CF1604A时代
罗蒂面条
题目大意
给定一个长度为(n)的序列(a_1，a_2，\dots，a_n\)，您可以一次向序列中插入任意整数，并找出至少要插入多少个整数。
题目分析
因为您想保留任何\(a_i\le i\)，所以很容易想到在\(a_{i-1}\)和\(a_i\)之间插入\(a_i-i\) \(1\)，因为\(a_)
因此，很容易得到\(\rm Idea-1\):
使用\(sum\)指示使序列满足条件的最小操作数。
对于每一个\(a_i\)，如果\(a_i\gt i\)，那么\(sum \得到sum (a_i-i)\)。
这个方法明显有缺陷，比如数据1 3 4。
\(a[2]2\)，\(sum\)在\(i=2\)时等于\(1 \)；实际顺序将变成1 1 3 4。
\(i=3\)，我们需要再次插入\(1\)，但实际上我们没有改变序列，所以我们发现我们的算法在这个时候会出错。
考虑到插入\(1\)后每个数据都会移动，我想到用另一个变量\(move\)来记录每个数据向后移动的次数。
不过，std::move 是关键字。今年 \(\rm CSP-J\) 有人在代码里使用了 move，惨遭爆零（
代码
const int ma=105
结构节点
{
int val
int mov
};
节点节点[ma]；
int n；
内嵌void init()
{
memset(节点，0，sizeof(节点))；
}
内联整数计算()
{
int sum=0；
for(寄存器int I=1；I=n；(一)
{
节点[i]。mov=总和；
if(节点[i]。valnode[i]。mov)
{
sum=节点[i]。val-node[i]。mov
}
}
返回总和；
}
int main(空)
{
int T=read()；
而(T -)
{
init()；
n=read()；
for(寄存器int I=1；I=n；(一)
{
节点[i]。val=read()；
节点[i]。mov=I；
}
printf(‘%d\n ‘，calc())；
}
返回0；
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/74736.html