[ARC153C] ± Increasing Sequence
构造严格递增的X序列,通过差分,可变为构造全为正的Y(首项除外)。
推公式可知,Y需要满足与B的内积为0,其中B是A的后缀和。
因A取值特殊,故B有一定性质。其中:若B有正有负,则一定有+1和-1。
先考虑B有正有负的情况:
先让Y全部为1,再看B的和 tot,+1的点可补偿tot<0情况,-1的点可补偿tot>0情况。
再考虑B无正整、或无负数情况:
因B不可能全0,所以一定需要补偿,而只有无约束的Y[1]能起到补偿的作用,
若B[1]为零,Y[1]不能发挥作用,无解,输出"No"。
若B[1]非零,则设Y[2...n]都为B[1]的绝对值,再安排Y[1]来补偿所有。