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

· · 题解

题解

考虑贪心。

第一步可以先观察出题人给的性质，发现性质为保证至少一个杯子中没有水，所以我们考虑当有一个杯子没有水时，显然可以互相交换且不会溢出。所以说一定是可以互相排序的。

然后考虑一个空杯子都没有的情况，发现可以直接构造出一个空杯子，然后就一定能把这个序列变成单调不降。所以直接将数组中的最小值和次小值叠在一起，直接统计出损失的水，然后输出即可。

但是这样做有一种情况，例如

5 25
20 21 22 23 24

观察到如果按上一种方法来做，是先将 a_1+a_2 这么多的水移到其中一个杯子中，显然会有溢出，然后算出结果肯定比正确答案要小，因为这个序列本身就是合法的，所以还需要判断一下数列本身是否合法，最后输出即可。

正确代码


#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);//总和减溢出的水
    }
}