CF1965A 题解

ikunTLE · 2024-06-08 21:38:52 · 题解

题目传送门

思路

由于答案与石子的数量有关，且每一次都可以将整个序列的高度降低 1，可以将降低高度的过程看作是差分。

接下来处理移除石子的最优解，就需要判断哪一方处于优势——处于优势的一方会一直处于优势。但是如果第一个石子是 1，优势就“发挥不出来”，只能判断最大的 a_k=k 的最大值。

由此得知，胜者取决于差分后第一个差值不为 1 时处于优势的人。

做法

1. 排序并去重（可以用set），差分。

2. 判断 a_i=1 的情况。

3. 找出第一个差值不为 1 时处于优势的人。