Lotuses's Blog

CF1649B Solution

  • 800 字
  1. 1. Solution

Solution

重点在于如何利用 “每个人传出球的次数是给定的（传入不算次数）。”

找出踢球数最大的人，这个人的踢球数可以消耗其他人的踢球数。

若其他人的踢球数总和大于踢球数的人，这些人可以自己内部对踢（无论是一对一还是多对多，反正剩下的踢球数等于最大踢球数）。

但如果最大踢球数的人踢球的数量太大了，他跟其他人消耗后，还剩下了一些球数，只能他自己踢了（为什么？最多的情况下，即剩下人不内部踢球，只与最大踢球数的人踢，也只能消耗这些，还差一些）。

所以，

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k,maxn=0,sum=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>k;
            maxn=max(maxn,k);
            sum+=k;
        }
        // sum-=maxn;
        // if(sum)
        if(maxn==0) cout<<0<<endl;
        else
        {
            int ans=max(1ll,maxn-(sum-maxn));
            cout<<ans<<endl;
        }
    }
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可