# 14207: 【原4207】大主教带队

### 题目描述

author: RayCiel 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4207

## Sample Input

5 2
1 2 15 15 15


## Sample Output

5


## ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int a[5009] = { 0 };

template <class T, class T_val = decltype(*declval<T>()),
class Compare = bool (*)(T_val, T_val)>
void quick_sort(T start, T end,
Compare cmp = [](T_val a, T_val b) {return a < b; }) {
if (start == end)
return;
auto i = start, j = end;
--j;
if (i == j)
return;
//交换
auto key = *start;
for (bool status = true; i != j;) {
if (status) {
if (cmp(*j, key)) {
*i = *j;
++i;
status = false;
}
else
--j;
}
else {
if (cmp(key, *i)) {
*j = *i;
--j;
status = true;
}
else
++i;
}
}
*i = key;
//递归
quick_sort(start, ++i, cmp);
quick_sort(i, end, cmp);
}

int dp_data[5000][5000] = { 0 };
int n;

int dp(int pos, int k) {
if (pos >= n || k <= 0) {
return 0;
}
if (dp_data[pos][k] > 0)
return dp_data[pos][k];
int ans1 = dp(pos + 1, k), ans2 = 0, i = pos;
for (; i < n; ++i) {
if (a[i] - a[pos] <= 5)
++ans2;
else
break;
}
ans2 += dp(i, k - 1);
dp_data[pos][k] = ans1 < ans2 ? ans2 : ans1;
return dp_data[pos][k];
}

int main() {
int k;
cin >> n >> k;

for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);

quick_sort(a, a + n);

cout << dp(0, k);

return 0;
}


## skyzh's solution

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Range {
Range(int L, int R) : L(L), R(R) {}
int L, R;
friend bool operator< (const Range& a, const Range& b) {
if ((a.R - a.L) == (b.R - b.L)) return a.L < b.L;
return (a.R - a.L) < (b.R - b.L);
}
};

int main() {
priority_queue <Range, vector<Range>, less<Range> > t;
int n, k;
int cap[10000] = { 0 };
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> cap[i];
sort(cap, cap + n);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (cap[i] - cap[j] <= 5) {
t.push(Range(j, i));
}
}
}
bool visited[10000] = { 0 };
while (!t.empty() && k > 0) {
Range r = t.top();
bool found = true;
for (int i = r.L; i <= r.R; i++) {
if (visited[i]) {
found = false;
break;
}
}
if (found) {
for (int i = r.L; i <= r.R; i++) {
visited[i] = true;
}
--k;
}
t.pop();
}
int sum = 0;
for (int i = 0; i < n; i++) if (visited[i]) ++sum;
cout << sum << endl;
return 0;
}