UmiQS' Blog
0%

[蓝桥杯][题解]对局匹配

发表于 更新于 分类于 ， Valine：

1.试题

问题描述

小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是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

样例输出

6

2.算法分析

分析积分序列，可以将用户的积分分组：

  • 0,k,2k,3k,…
  • 1,k+1,2k+1,…
  • …
  • k-1,2k-1,3k-1,…

可以看出，不同分组用户之间是不可能匹配成功的，因为他们之间的积分差不可能为k，所以我们需要分别在每一组中求出所能选择的最大人数。

设某一组中的积分序列为$\{score[1],score[2],…,score[t]\}$，显然相邻的两个元素（积分）$score[i-1]$和$score[i]$不能同时选,但是积分$score[i-2]$却能和$score[i]$同时选择。因此，当计算到第$i$个元素时，该元素是否选择只和第$i-1$和第$i-2$的状态有关。

考虑动态规划。

设$f[i]$为在某一分组下，当选到第$i$个元素是能够同时选择的最大人数，$cnt[i]$为积分等于$i$的人数，则有

将K个分组的$f[t]$加起来，就是最后的答案$ans$。

时间复杂度：$O(MaxSore)$，即输入的最大积分。

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//group + DP
#include<iostream>
#include<cstdio>
#define MAXN 100000
using namespace std;

int n,K,ans;
int num[MAXN+5]={0},f[MAXN+5]={0},Hash_[MAXN+5]={0};

int main()
{
    int i,j,x;
    cin>>n>>K;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        Hash_[x]++;
    }
    ans=0;
    if(K==0)//特殊处理 
    {
        for(i=0;i<=MAXN;i++)
          if(Hash_[i]) ans++;
    }
    else
    {
        for(i=0;i<K;i++)
        {
            int m=0;
            for(j=i;j<=MAXN;j+=K) num[++m]=Hash_[j];//不能有 if(Hash_[j])  
            f[1]=num[1];
            for(j=2;j<=m;j++)
            {
                f[j]=max(f[j-1],f[j-2]+num[j]);
            }
            ans+=f[m];
        }
    }
    cout<<ans<<endl;
    return 0;
}