CF1891C Smilo and Monsters

CF1891C Smilo and Monsters

题目链接

题目大意

给出一个长度为 $n(1 \leq n \leq 2*10^5)$ 的数组 $a_i(1 \leq a_i \leq 10^9)$ ，你可以进行以下两个操作

• 将其中任意一个数的值减少 $1$ ，并使你的计数器 $cnt++$ ，

• 将其中任意一个数的值减少 $cnt$ ，并使你的计数器 $cnt$ 归零

求使一个数组所有元素归零的最小操作数

思路

不难发现，我们可以先把数组中较小的数用第一个操作归零，然后把数组中较大的数用第二个操作归零，这样做最大化利用 $cnt$ ，可以确保操作数是最小的

所以先将数组从小到大排序一下，用双指针 $l,r$ 分别指向数组的头和尾，再按照贪心思路进行模拟即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=2e5+1;
int awa[maxn];
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read();
        for(int i=1;i<=n;i++) awa[i]=read();
        sort(awa+1,awa+1+n);
        int l=1,r=n,cnt=0,ans=0;
        while(l<=r)
        {
            if(l==r)
            {
                if(!awa[l]) break;
                if(!cnt) {ans+=awa[l]==1?1:(awa[l]+3)/2;break;}
                else {ans+=(awa[l]-cnt+3)/2;break;}
            }
            if(cnt+awa[l]>=awa[r])
            {
                awa[l]-=awa[r]-cnt;
                ans+=awa[r]-cnt+1,cnt=0,r--;
                if(!awa[l]) l++;
            }
            else cnt+=awa[l],ans+=awa[l],l++;
        }
        write(ans),puts("");
    }
    return _123hh2;
}