解题思路
全部货位最初都在册,翻转偶数次等价于不操作,翻转奇数次等价于下线一次。最优解只会把若干货位各下线一次,不会把已经下线的再翻回来。问题转化为:从序列中删去最少个数,使剩余数中不存在两个(可相同下标以外)之和等于阈值 t。
按数值分组统计出现次数后,冲突只可能发生在数值对 (x,t−x) 上,且各组互不干扰:
- 若 x=t−x,即 2x=t:只要两侧都还剩至少一个,就一定能配成冲突。必须删光其中一侧,最少删除次数为 min(cnt(x),cnt(t−x))。
- 若 x=t−x,即 2x=t:任意两个 x 都能配成冲突,至多保留 1 个,最少删除 max(0,cnt(x)−1)。
- 每对只统计一次,避免把 (x,t−x) 与 (t−x,x) 加两遍。