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

· · 题解

其实本来我做出来第一题就不想做第二题了，同学强迫我做的。

思路

这道题一眼贪心。

那么怎么贪呢。

我们通过 30 分的数据，可以发现，只要有至少一个空杯子就一定能进行没有损失的排序。

证明很好证，比如说有一个空杯子，那么我们排序时向前排，就能把前面比他小的数字放到空杯子，然后当前的数字向前移，再把替换的数放到空出来的位置。

那么，我们发现，那如果直接进行排序肯定没有腾出一个空杯子更优。

于是，我们对原数组排序，合并两个水最少的杯子，腾出位置，这样子可以做到最小损失。

然后，我们在进行求和。

但是，完了吗？

我们发现，这样子我们还是只有 30 分。

我们看个例子：

10 100
100 100 100 100 100 100 100 100 100 100

应该输出1000，但我们的代码输出900。

这说明我们的代码对于数组本身就是排好序时且数字为 m 时无法正确处理。

那么，统一一下，如果数组本身有序，直接输出整个数组的和即可。

那么，我们在一开始的代码判断一下序列是不是有序的就行了。

代码

#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;
    }
}