1 条题解

  • 1
    @ 2024-7-21 20:00:10

    求出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
    上传者