题解：P9780 [HUSTFC 2023] Azur Lane

· · 题解

知识点：

就是一道板子贪心题。

思路：

当 n=m 时，刚好每天都放一个喵箱，可使用等差数列求和公式（高斯公式）计算：

再看题面：在每天结束时系统会自动扣除与喵窝中喵箱数量相等的钱。 易知，在越晚的时候放喵箱，花费就越少。

例如：在 \texttt{3} 天中放入了 \texttt{6} 个喵箱（保证为单调不上升序列）：

最差：第一天 \texttt{4} 个，第二天 \texttt{1} 个，第三天 \texttt{1} 个，花费 4+5+6=15 元；

最好：第一天 \texttt{1} 个，第二天 \texttt{1} 个，第三天 \texttt{4} 个，花费 1+2+6=9 元；

贪心策略：很明显，在越后面的天数放喵箱，花费越少。

那代码怎么写呢？我们先倒序判断，只要当前值不小于之前的值，那么我们就可以付钱，并记录更新。

最后，在从头遍历一遍，如果答案数组的位置非 \texttt{0}，输出即可，如果为 \texttt{0}，输出 \texttt{-1} 即可。

注意事项：

1.本题数据范围：k\ (1 \leq k \leq 10^6)，需开 long long！！！

2.注意答案数组的更新，并小心公式数值溢出！

我的代码（有注释，仅供参考）：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+10;
int n,m,k,s[N],ans[N],sum;
signed main()
{
    cin>>m>>k;
    ans[m]=(1+m)*m/2; //等差数列求和公式（n=m时，求总和即可）；
    sum=m-1;
    for(int i=1;i<=m;i++){
        cin>>s[i];
    }
    for(int i=m-1;i>=1;i--){//倒序判断
        if(s[i]>=s[i+1]){//默认大的在前面，否则无解
            ans[sum]=ans[sum+1]-i;//可以为之花费，并记录钱数；
            sum--;
        }
    }
    for(int i=1;i<=m;i++){
        if(ans[i]){//当前位置有选择（非0）；
            cout<<ans[i]<<" ";
        }else{//反之输出-1；
            cout<<-1<<" ";
        }
    }

    return 0;
}