蓝桥杯 对局匹配c++
这个题目用自己的笨办法试了一下,AC成功。例如当K=2时,可分为 {0, 2, 4, 6, 8, …},{1,3, 5, 7, 9, …}共2组。可以发现不同组的数无论如何选择,都不可能相互间相差K,那么我们只需要求每组选出的最大人数之和即可。0作为一个特殊情况只需要判断和自己是否相等的数就行,剩下的情况设一个数据范围来比较,用时能相对短一些。#include <stdio.h>...
·
这个题目用自己的笨办法试了一下,AC成功。
例如当K=2时,可分为 {0, 2, 4, 6, 8, …},{1,3, 5, 7, 9, …}共2组。可以发现不同组的数无论如何选择,都不可能相互间相差K,那么我们只需要求每组选出的最大人数之和即可。
0作为一个特殊情况只需要判断和自己是否相等的数就行,剩下的情况设一个数据范围来比较,用时能相对短一些。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX_SCORE 100000
const int maxn = 100000 + 5;
int cnt[MAX_SCORE+5], val[maxn], dp[maxn];
int n, k;
int main() {
while(scanf("%d%d", &n, &k) == 2) {
memset(cnt, 0, sizeof(cnt));
int score, ans = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &score);
cnt[score]++;
}
if(k == 0) {//特殊处理,不然0如果考虑进去浪费时间
for(int i = 0; i <= MAX_SCORE; i++) {
if(cnt[i]) ans++;
}
}
else {
for(int i = 0; i < k; i++) {
int m = 0;
for(int j = i; j <= MAX_SCORE; j+=k) {
val[m++] = cnt[j];
}
dp[0] = val[0];
for(int j = 1; j < m; j++) {
if(j == 1) dp[j] = max(dp[0], val[j]);
else dp[j] = max(dp[j-2] + val[j], dp[j-1]);
}
ans += dp[m-1];
}
}
printf("%d\n", ans);
}
return 0;
}
更多推荐
已为社区贡献2条内容
所有评论(0)