CF1119A Ilya and a Colorful Walk 题解

liruixiong0101 · 2023-06-09 17:05:44 · 题解

P0 前置知识：

贪心，一点点数学。

P1 题意：

给你 n 和 n 个数 a_1,a_2,\dots,a_n，让你求出 \max\{a_i-a_j\}(1\le i\lt j\le n,a_i\neq a_j)。

P2 思路：

本题有两种做法。

第一种做法：

第一种做法就是贪心，由于需要让两个数的距离最远且不相等，若不考虑不相等的条件，肯定是要让初始位置最小，最终位置最大。

设 c_{0,i} 为 a_j=i 的 最小的 j，c_{1,i} 为最大的 j。
那么不考虑不相等的条件的话，答案就是 \max\{c_{1,i}\}-\max\{c_{1,j}\}(i\le m,j\le m)（m 为 a 数组去重后的种类数）。

如果考虑不相等的条件的话，就要判断 \max\{c_{1,i}\} 的 i 不等于 \max\{c_{1,j}\} 的 j 即可。实现这样的操作可以用结构体加排序解决。

https://codeforces.com/problemset/submission/1119/209101521

第二种做法：

考虑最极端情况答案最大为 n-1，但前提是 a_1\neq a_n。
若 a_1 = a_n 怎么办呢？
手造几个 a_1\neq a_n 的样例可以发现答案的最大值的左右端点总是包含 a_1 或 a_n，我们猜测答案的左右端点一定包含 a_1 或 a_n，我们需要证明这一点。

若答案区间为 [i,j](i\neq 1,j\neq n)。
我们考虑把 i 挪到 1 的位置，若 a_1\neq a_i 的话，答案显然比 [i,j] 好，若 a_1=a_i，因为 a_i\neq a_j,a_1\neq a_n,a_1=a_i 所以 a_i\neq a_n 这样的答案也一定比 [i,j] 好，所以我们的猜想成立。

接下来代码就很好写了。

https://codeforces.com/problemset/submission/1119/209073882