rt,上一篇帖子提到第一篇题解不能通过 hack 数据,而第二篇题解能照常通过:
4 18 2 3
18 2 4 14
我经过对比发现第二篇题解有一个很特别的地方,就是对输入的数据进行了处理:
if(a[i]<1ll*(i-1)*l+1){
ext+=abs(a[i]-(1ll*(i-1)*l+1));
a[i]=1ll*(i-1)*l+1;
}
删除这段代码,第二篇题解不仅不能 AC,hack 数据构造出的方案也是 0 2 4 7
,不符合题意。反过来,第一篇题解的代码加上这段处理后,不仅能通过 hack 数据,还能照常 AC。
感性理解一下根据题目的要求第 i 个数字至少是 (i−1)×A+1。
但遗憾的是第二篇代码并没有详细地讲解值域的边界处理,比如超过 Q 的数的处理。也没有讲为什么要这么预处理。我想知道这段代码真的是必要的吗?可不可以通过某种写法规避掉这种问题?直接暴力转移也需要这样的预处理吗?