蓝桥杯2017年第八届真题-对局匹配 （C++代码）

解题思路:    

    把所有的数整理列表，用数组下标表示可能的积分值，对应的数组储存该积分出现的次数，并在第一次输入时记录输入的最大积分值maxn。

    分组，积分差k为2就分两组，一组0，2，4……maxn；一组1，3，5，……maxn这样，用i和j两个下标搜寻，在i和j两个积分制之间比较，留下积分值多的那个。如果i和j中有一个积分值出现了0次当然就可以直接留下不为0的那个数，然后i=i+k,j=i+k继续往后判断；如果i和j表示的积分值都不为0则还需要判断第三个j+k的数出现次数。

    总之，在积分差为k的相邻两个或三个数中留下出现次数多的，把出现次数少的赋值为0，最后在统计数组中留下来的数。

    其实我感觉似乎还有些问题，但不会dp就这么暴力也过了，欢迎大家指教！

    

注意事项:当k为0时需要特殊处理。

参考代码:

// 1842 对局匹配  3/12
#include<iostream>
#include<cstdio>
using namespace std;
int a[100000+5];
int b[100000+5] = {0};
int maxn=0;
int main(){
 int n,k;
 cin>>n>>k;
 for(int i=1;i<=n;i++){
  cin>>a[i];
  if(a[i]>maxn) maxn=a[i];
  b[a[i]]++;
 }
 
 for(int r=0;r<=k;r++){
  if(k==0) k=1;
  for(int i=r,j=i+k;j<=maxn;){
   if(b[i]*b[j]==0){
    i=j;
    j=i+k;
    continue;
   }
   else{
    int p=j+k;
    if(b[p]==0){
     if(b[i]<b[j]) b[i] = 0;
     else b[j] = 0;
     i=p+k;
     j=i+k;
    }
    else{
     int q=b[i]+b[p];
     if(b[j]<q) b[j] = 0;
     else b[i]=b[p]=0;
     i=j;
     j=i+k;
    }
   } 
  }
  if(k==0) break;
 }
 
 int ans=0;
 for(int i=0;i<=maxn;i++) ans+=b[i];
 cout<<ans;
 return 0;
}