自动搬运

查看原文

来自洛谷，原作者为

	uncle_steve 当你凝望OI时，OI也在凝望你 || Farmer John的奶牛数？

搬运于2025-08-24 22:51:47，当前版本为作者最后更新于2024-11-30 20:53:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

知识点：

就是一道板子贪心题。

思路：

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

• $\displaystyle\sum_{i=1}^{n} i$ 。

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

例如：在 $\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;
}