专栏文章

题解：P14057 【MX-X21-T2】[IAMOI R5] 空气蛹

TTCY1234567
P14057题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintf9je
此快照首次捕获于
2025/12/02 08:03
3 个月前
此快照最后确认于
2025/12/02 08:03
3 个月前
查看原文

题解

考虑贪心。
第一步可以先观察出题人给的性质，发现性质为保证至少一个杯子中没有水，所以我们考虑当有一个杯子没有水时，显然可以互相交换且不会溢出。所以说一定是可以互相排序的。
然后考虑一个空杯子都没有的情况，发现可以直接构造出一个空杯子，然后就一定能把这个序列变成单调不降。所以直接将数组中的最小值和次小值叠在一起，直接统计出损失的水，然后输出即可。
但是这样做有一种情况，例如
CPP
5 25
20 21 22 23 24
观察到如果按上一种方法来做，是先将 a1+a2a_1+a_2 这么多的水移到其中一个杯子中，显然会有溢出，然后算出结果肯定比正确答案要小，因为这个序列本身就是合法的，所以还需要判断一下数列本身是否合法，最后输出即可。

正确代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],b[100005];
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n,m;
		scanf("%lld%lld",&n,&m);
		int sum = 0;
		int flag = 0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			b[i] = a[i];
			sum+=a[i];
			if(a[i]>=a[i-1]&&i!=1) flag++;
		}
		if(flag==n-1)//如果成立，证明这个数列就是单调不降的
		{
			printf("%lld\n",sum);
			continue;
		}
		sort(b+1,b+n+1);
		int ans = 0;
		if(b[1]+b[2]>m) ans = b[1]+b[2]-m;
		else ans = 0;
		printf("%lld\n",sum-ans);//总和减溢出的水
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...