1 条题解
-
1
求出a得差分序列b,题目中要求对a的操作,相当于每次可以选出b1,b2,b3...bn中的任意两个数,一个加一,一个减一。目标是把b2,b3...bn变为全零。最终还原出来的数列a就是由n个b1构成的。 从b1,b2...bn中任选两个数的方法可以分为四类: 1.选bi & bj,其中2<=i,j<=n。这种操作会改变b2,b3...bn中两个数的值。应该保证bi & bj一正一负的前提下,尽量多的使用这种操作,以更快的接近答案。 2.选b1 & bj,其中的2 <= j <= n 3.选bi & bn,其中2 <= i <= n 4选b1 & bn,这种情况没有意义,因为他不会改变b2,b3...bn的值,相当于浪费了一次操作。 设b2,b3...bn中的正数总和为p,负数总和的绝对值为q 然后我们通过提前人工得出结论,达到结果的步数为min(p,q) + |p - q| = max (p , q);序列的可能性为|p - q| + 1种;
- 1
信息
- ID
- 427
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 280
- 已通过
- 63
- 上传者