题解 CF1305E 【Kuroni and the Score Distribution】

皎月半洒花

2020-03-06 08:09:17

Solution

比较自然的想法是从头开始填 $1,2,3\cdots$,因为这样容易填且满足条件。同时可以发现,这种构造方式是使得每个位置作为 $k$ 时,贡献三元组最多的方式:由于序列满足单调性,所以一定不存在前面的 $i,j$ 彼此有交。那么对于一个 $a_k=k$ 他可以贡献 $\lfloor \frac{k-1}{2}\rfloor$ 的答案。 考虑如果超出 $m$ 如何处理。假设当前答案超出了 $x$ 。对于一个 $k$ ,按照上述方式能够贡献 $\lfloor \frac{k-1}{2}\rfloor$ 的答案,那么如果想要只贡献 $\lfloor \frac{k-1}{2}\rfloor-x$ 的答案,就需要让其中的 $x$ 对 $(i,j)$ 无效。具体的,考虑令当前的 $k$ 变为 $k+2x$ ,那么考虑前 $k-1$ 个数里面最大的是 $k-1$ ,只能去匹配 $2x+1$,这样就会少掉 $2x$ 个可以用的数,答案变成了 $\lfloor\frac{k-1-2x}{2}\rfloor=\lfloor \frac{k-1}{2}\rfloor-x$ 。 那么补齐 $n$ 个数也很简单。只需要考虑如果当前填了的最大的数是 $j$ ,从 $10^9$ 向下按照 $2\cdot j$ 的步长递减即可。不难证明这样做是对的。 ```cpp int main(){ std :: cin >> n >> m ; for (int i = 1 ; i <= n ; ++ i){ ans[i] = i ; cnt += (i - 1) / 2 ; if (cnt >= m){ int s = 1000000000 ; ans[i] += 2 * (cnt - m) ; for (int j = n ; j > i ; -- j) ans[j] = (s -= (ans[i] + 1)) ; gf = 1 ; break ; } } if (gf) for (int i = 1 ; i <= n ; ++ i) printf("%d ", ans[i]) ; else return puts("-1"), 0 ; } ```