自动搬运

查看原文

来自洛谷，原作者为

	追梦之鲸 哼~

搬运于2025-08-24 22:21:17，当前版本为作者最后更新于2021-01-02 21:16:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本蒟蒻的第$002$篇题解。

经典回顾P6490

思路

这道题是一个很简单的贪心题。

直解从$n-1$倒序枚举即可。

详解

• 首先这到题必须严格递增，也就是没个数必须比下个数小，比上个数大，相等不行！

• 说一下为什么从$n-1$倒序枚举，而不从$1$正序枚举？对于不懂这类的同学（比如窝），可能窝给出一组数据你们大概就能理解：

5 6 7 4

这组数据用刚才正序枚举的思想的话答案是0，实际答案是12。

可能还有同学不懂，那么下面我会更详细的解说：

这题说需要求出所有减去的数的总和的最小值，所以必须保证最后面的数最大（你可以理解为最后的数不变）。

然后从第$n-1$个数起，如果第$i$个数比第$i+1$个数大，第$i$个数就等于第$i+1$个数-1。

还有这里介绍一下可能对你有帮助的register int和快读快输

链接

• register int

这个register int中的register 表示使用cpu内部寄存器（寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件）的变量，而平时的int是把变量放在内存中，存到寄存器中可以加快变量的读写速度。

• 快读与快输

链接

模板

//快读
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
//快输
inline void write(int X)
{
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) write(X/10);
	putchar(X%10+'0');
}
或
inline int write(int X)
{
	if(X<0) {putchar('-'); X=~(X-1);}
	int s[20],top=0;
	while(X) {s[++top]=X%10; X/=10;}
	if(!top) s[++top]=0;
	while(top) putchar(s[top--]+'0');
}

code：

#include<bits/stdc++.h>//无敌头文件！
#define ll long long
#define il inline
#define ri register int
using namespace std;
il int rd(){
   int s=0;
   char ch=getchar();
   while(ch<'0'||ch>'9') ch=getchar();
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s;
}
il void wt(int x){
	if(x>9) wt(x/10);
	putchar(x%10+'0');
	return;
}
//快读与快输
int n,a[101],dan;
int main(){
	n=rd();
	for(ri i=1;i<=n;i++) a[i]=rd();
	//本题的精髓
	for(ri i=n-1;i>=1;i--) if(a[i]>=a[i+1]){dan+=a[i]-a[i+1]+1;a[i]=a[i+1]-1;}
	wt(dan);
	return 0;
	撒花✿✿ヽ(°▽°)ノ✿
}

最后管理大大求过&&来玩啊