专栏文章

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

wweifengzhaomi
P14057题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minttfsw
此快照首次捕获于
2025/12/02 08:14
3 个月前
此快照最后确认于
2025/12/02 08:14
3 个月前
查看原文
其实本来我做出来第一题就不想做第二题了，同学强迫我做的。

思路

这道题一眼贪心。
那么怎么贪呢。
我们通过 3030 分的数据，可以发现，只要有至少一个空杯子就一定能进行没有损失的排序。
证明很好证，比如说有一个空杯子，那么我们排序时向前排，就能把前面比他小的数字放到空杯子，然后当前的数字向前移，再把替换的数放到空出来的位置。
那么，我们发现，那如果直接进行排序肯定没有腾出一个空杯子更优。
于是，我们对原数组排序，合并两个水最少的杯子，腾出位置，这样子可以做到最小损失。
然后，我们在进行求和。
但是，完了吗？
我们发现，这样子我们还是只有 3030 分。
我们看个例子：
CPP
10 100
100 100 100 100 100 100 100 100 100 100
应该输出1000，但我们的代码输出900。
这说明我们的代码对于数组本身就是排好序时且数字为 mm 时无法正确处理。
那么，统一一下，如果数组本身有序，直接输出整个数组的和即可。
那么，我们在一开始的代码判断一下序列是不是有序的就行了。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m,ans,a[200000];
inline bool clec(){
	for (int i = 1;i < n;i++) if (a[i] > a[i + 1]) return false;
	return true;
}
signed main(){
	cin >> t; while (t--){
		cin >> n >> m,ans = 0;
		for (int i = 1;i <= n;i++) cin >> a[i];
		if (clec()){
			for (int i = 1;i <= n;i++) ans += a[i];
			cout << ans << endl;
			continue;
		}
		sort(a + 1,a + n + 1);
		a[2] += a[1];
		a[1] = 0;
		if (a[2] > m) a[2] = m;
		for (int i = 1;i <= n;i++) ans += a[i];
		cout << ans << endl;
	}
}

评论

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

正在加载评论...