CF1891C Smilo and Monsters - CF题解 | 123hh2 = Keep moving forward

# CF1891C Smilo and Monsters

题目链接

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

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

不难发现，我们可以先把数组中较小的数用第一个操作归零，然后把数组中较大的数用第二个操作归零，这样做最大化利用 $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;
	}