CF1692H Gambling 题解

发布时间 2023-12-03 21:54:40作者: ShawyYum

题意:

思路:

考虑离散化:

枚举 $ x $ 中出现的每一个数 $ val $ , $ val $ 出现的次数为 $ cnt $ ,记录 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ 。设 $ x $ 中与 $ val $ 相等的数贡献为 $ +1 $ ,与 $ val $ 不相等的数贡献为 $ -1 $ ,那么问题转化为最大连续子段和。

由于已经知道 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ ,设区间初始左端点 $ l = idx_1 $ ,区间初始右端点 $ r = idx_1 $ ,最大连续子段和 $ ans = 1 $ ,$ for \space i : 2 \to cnt - 1 $ 枚举每个区间右端点 $ r = idx_i $ ,当区间 $ [l,r] $ 贡献为 $ sum \le 0 $ 时,更新区间左端点为 $ l = idx_i $ ;否则,继续统计区间贡献 $ sum $ , $ ans = max(ans, sum) $ 。

对 $ x $ 中出现的每一个数 $ val $ 进行上述过程即可。