Link

CF1891 C Smilo and Monsters

Question

有 \(n\) 个怪物部落，其中 \(a_i\) 表示第 \(i\) 个部落中的怪物数量，你有一个值 \(x\) 初始为 \(0\) ，你有两种方式来消灭所有的怪物

选中一个怪物数量大于 \(1\) 的部落，消灭一个怪物，然后 \(x+=1\)
大招，选中一个怪物数量大于 \(x\) 的部落，消灭 \(x\) 个怪物，然后 \(x=0\)

Solution

通俗的讲，我们把 \(x\) 理解为游戏里面的 “气”

通过题目可以知道 “气” 不会浪费，也就是说，\(x+1\) 了后，在放大招的时候一定会用掉

所以我们很容易得到一个结论：放大招的次数越少越好

贪心的去想，肯定要把 “气” 攒的越多越好，然后用一个大招，把怪物数量多的部落干掉

所以排序，每次用小的部落来攒 “气” 攒到能干掉目前最大的那个就好了

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
const int maxn=2e5+5;
int N,a[maxn];
void solve(){
    N=read();
    int ans=0;
    for(int i=1;i<=N;i++)a[i]=read();
    sort(a+1,a+1+N);
    int hed=1,til=N;
    int now=0,big;
    while(hed<=til){
        big=a[til];
        if(hed==til){
            printf("%lld\n",ans+min(a[til],(a[til]+1)/2+1));
            return;
        }
        while(hed<til&&now<=big) 
            now+=a[hed++];
        if(now<=a[til]){
            if(now==big){
                ans+=now+1;printf("%lld\n",ans);return ;
            }
            else{
                int derta=(a[til]-now)/2;
                if(now==0&&a[til]==1)
                    printf("%lld\n",ans+1);
                else 
                    printf("%lld\n",ans+now+derta+1+(a[til]-now-derta*2));return;
            }
        }
        else{
            ans++;ans+=big;til--;
            if(now!=big)
                a[--hed]=now-big;
            now=0;
        }
    }
    printf("%lld\n",ans);
}
signed main(){
    // freopen("C.in","r",stdin);
    // freopen("C.out","w",stdout);
    int T=read();
    while(T--) solve();
    return 0;
}