洛谷题面

题目大意

给一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)，每次可以往序列中插入任意个整数，求最少插入多少个整数时 \(\forall i,a_i\le i\)。

题目分析

既然想要保持任意 \(a_i\le i\)，那么容易想到在 \(a_{i-1}\) 和 \(a_i\)之间插入 \(a_i-i\) 个 \(1\)，因为 \(a_i\ge1\)，所以一定满足条件。

所以容易得出 \(\rm Idea-1\)：

用 \(sum\) 表示使序列满足条件的最少操作数量。

对于每一个 \(a_i\)，若 \(a_i\gt i\)，那么 \(sum\gets sum+(a_i-i)\)。

这种方法显然是有漏洞的，比如数据 1 3 4。

\(i=2\) 时，\(a[2]>2\)，\(sum\) 等于 \(1\)；实际的序列会变成 1 1 3 4。

\(i=3\) 时，又一次需要插入 \(1\)，但是实际上我们并没有改变序列，所以我们发现此时我们的算法会出现错误。

考虑到每个数据在插入 \(1\) 后都会移动，于是想到再用一个变量 \(move\) 来记录每个数据向后移动的个数。

不过，std::move 是关键字。今年 \(\rm CSP-J\) 有人在代码里使用了 move，惨遭爆零（

代码

const int ma=105;

struct Node
{
	int val;
	
	int mov;
};

Node node[ma];

int n;

inline void init()
{
	memset(node,0,sizeof(node));
}

inline int calc()
{
	int sum=0;
	
	for(register int i=1;i<=n;i++)
	{
		node[i].mov+=sum;
		
		if(node[i].val>node[i].mov)
		{
			sum+=node[i].val-node[i].mov;
		}
	}
	
	return sum;
}

int main(void)
{
	int T=read();
	
	while(T--)
	{
		init();
		
		n=read();
		
		for(register int i=1;i<=n;i++)
		{
			node[i].val=read();
			
			node[i].mov=i;
		}
		
		printf("%d\n",calc());
	}
	
	return 0;
}