这题老师讲了没听懂！！！ 
3 个赞
对于任意的i，最终要使得a[i]=a[n-i+1]
所以求出s[i]表示要操作多少次a[i]使得a[i]>=a[n-i+1].
所以问题转化成了在s中可将连续的数减一，要多少次才能让s变成0.
考虑使用差分，记差分后的数组为cut[i]
cut[i]表示连续的操作解决不了i的部分。
用双指针遍历数组，现有cut[i]>0, cut[j]>0, cut[i-1]<=0, cut[j+1]<=0, 且i~j间cut为正
所以答案就是∑∑k=i~j cut[k].
因为cut是s的差分数组，答案即为∑cut[j]-cut[i-1].
5 个赞
谢谢~
4 个赞
谢谢你们
4 个赞
谢谢
4 个赞