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