CF1649B 题解

· · 题解

UPD:

修理了一些空格问题，修了一下爆炸的 markdown。

前言：

赛场上想了一个做法但自认为是错的，结果赛后看了官方题解做法差不多
我自认为球可以自己传给自己，如果错了请大佬指出来。

题目大意：

有 n 个球员，每两个球员之间可以互相传球。
给定一个长度为 n 的数组 a，a_i 代表第 i 个球员传球次数。
问最少有多少个球。

题目分析：

模拟一下，可以发现第个球员可以消掉 a_i \cdot 2 个传球次数（其中 a_i 个球是消掉自己的传球次数，另外 a_i 个球是消掉别人的传球次数）。
也就是说，让他们互相抵消就行了，一对球员互相消完之后再传给下一个球员继续。最后如果只剩下了一个球员没有消完，假设这个球员还剩下 x 个球，那么再拿来 x 个球，自己传给自己就行了。
最后方法就是：

  1. 定义一个变量 imax 代表 a 数组中所有元素的最大值。
  2. 定义一个变量 cnt 代表 \Sigma^{n}_{i} a_i
  3. 如果 imax \cdot 2 \le cnt，那么只需要一个球，原因是模拟让一个球员去消掉别的所有球员的传球次数的情况，如果自己会被消掉，说明所有球员一定可以通过某种方案互相消掉。
  4. 如果 imax \cdot 2 \ge cnt+1，那么需要 imax \cdot 2 - cnt 个球，原因是模拟让一个球员去消掉别的所有球员的传球次数的情况，如果自己不会被消掉，说明无论如何一定不能只通过一个球，使所有球员互相消掉。需要引入 imax \cdot 2 - cnt 个球使得最后剩下没被消掉的球员通过自己传给自己把自己传球次数消掉。

注：
需要判断所有球员传球次数都为 0 的情况。

AC代码：

#include <bits/stdc++.h>
using namespace std;
int t,n;
const int maxn=1e5+5;
typedef long long ll;//hacker造出了爆int的数据！
int a[maxn];
ll cnt=0;
int imax;
bool flag;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag=1;
        scanf("%d",&n);
        imax=-1;
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            imax=max(imax,a[i]);
            cnt+=(ll)a[i];
            flag&=(a[i]==0);
        }
        if(flag)
        {
            printf("0\n");
            continue;
        }
        if(((ll)imax<<1)<=cnt)
        {
            printf("1\n");
        }
        else{
            printf("%lld\n",(ll)(imax<<1)-cnt);
        }
    }
    return 0;
}