蓝桥杯历届试题对局匹配

问题描述

　　小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。

　　小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。

　　现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, ... AN。

　　小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？

输入格式

　　第一行包含两个个整数N和K。
　　第二行包含N个整数A1, A2, ... AN。

　　对于30%的数据，1 <= N <= 10
　　对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000

输出格式

　　一个整数，代表答案。

样例输入

10 0
1 4 2 8 5 7 1 4 2 8

样例输出

将分数分组，相邻分数差为k，可能分为多组，每组中都尽量选择不相邻且人数多的。

转移方程的dp[i] = max(dp[i-2]+pi,dp[i-1]), pi为当前分数的人数。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <cmath>
 6 #define MAX_N 100005
 7 
 8 using namespace std;
 9 
10 int n,k;
11 int cnt[MAX_N];
12 int con[MAX_N];
13 int dp[MAX_N];
14 int ans;
15 int main()
16 {
17     cin>>n>>k;
18     int score,maxx = 0,temp = 0;
19     for(int i = 1; i <= n; i++)
20     {
21         cin>>score;
22         cnt[score]++;
23         maxx = max(maxx,score);
24         if(cnt[score]==1)
25             temp++;
26     }
27     ans = 0;
28     if(k==0)
29         ans = temp;
30     else
31     {
32         for(int i = 0; i < k; i++)
33         {
34             int pos = 0;
35             for(int j = i; j <= maxx; j+=k)
36             {
37                 con[pos++] = cnt[j];
38             }
39             dp[0] = con[0];
40             for(int j = 1; j < pos; j++)
41             {
42                 if(j==1)
43                     dp[j] = max(dp[0],con[1]);
44                 else
45                     dp[j] = max(dp[j-2]+con[j],dp[j-1]);
46             }
47             ans+=dp[pos-1];
48         }
49     }
50     cout<<ans<<endl;
51     return 0;
52 }

蓝桥杯 历届试题 对局匹配

蓝桥杯历届试题对局匹配