P8656对局匹配

xiaoxiaoxia · 2023-05-03 10:52:36 · 题解

题目分析：

题目给定了 N 名用户的积分，以及系统只会匹配积分差为 K 的两名用户。现在需要计算最多有多少名用户在线寻找对手时，系统却一场对局都匹配不起来。

解题思路：

1. 用一个数组 a 记录每个积分出现的次数。
2. 遍历数组，用贪心算法计算无法匹配的用户数。

   解题步骤：

3. 读取输入，得到用户数量 n 和积分差 k。
4. 遍历用户，读取每个用户的积分 x，并在数组 a 中增加对应的计数。
5. 初始化无法匹配的用户数 ans 为 0。
6. 如果 k 等于 0，说明只有积分相同的用户才能匹配，遍历数组 a，统计有积分的用户数，输出结果并返回。
7. 遍历数组 a 中的积分 i（0 到 \text{MAXN}-k），对于每个积分 i，计算无法匹配的用户数：
   • 如果a_{i} < a_{i+k}，说明积分差为 k 的用户更多，将 a_{i+k} 减去a_{i}。
   • 否则，将 a_{i+k} 置为 0。
8. 遍历数组 a 中的积分 i（0 到 \text{MAXN}-k），累加无法匹配的用户数。
9. 输出结果。

   代码部分

   #include<bits/stdc++.h>
   using namespace std;
   #define MAXN 100010
   int a[MAXN];
   int n, k, x;
   int main()
   {
   scanf("%d%d",&n,&k);
   for(int i=0;i<n;i++) 
   {
       scanf("%d",&x);
       a[x]++; 
   } 
   int ans=0;
   if(k==0) 
   {
       for(int i=0;i<MAXN;i++)
       {
           if(a[i]) 
           {
               ans++;
           }
       }
       printf("%d\n",ans);
       return 0;
   }
   for(int i=0;i<MAXN-k;i++) 
   {
       if( a[i]<a[i+k]) 
       {
           a[i+k]-=a[i];
       } 
       else 
       {
           a[i+k]=0;
       }
   }
   for (int i=0;i<MAXN-k;i++) 
   {
       ans+=a[i];
   }
   printf("%d\n",ans);
   return 0;
   }