CF1945E 解题报告

思路：分类讨论。 先要想到一个性质：若 $x$ 在二分过程中没有作为 $p_m$ 进行比较，则二分结束后将 $x$ 与 $p_l$ 交换，并不会影响原来二分的运行过程。 1. 二分结束后 $p_l = x$。 此时显然不用交换，已经满足题意。输出 ``0`` 即可。 2. 二分结束后 $p_l \neq x$。 * $p_l < x$。这时，我们要考虑 $x$ 在二分过程中是否作为 $p_m$ 进行比较过。 若是，那么当 $x = p_m$ 的时候，$l$ 是要赋为 $m$ 的，此时 $p_l = x$。那为什么最后 $p_l < x$ 呢？显然，在此次判断之后，$l$ 还被更新过至少 $1$ 次。我们考虑将二分结束后的 $p_l$ 与 $x$ 交换后，会发生什么。由于 $p_l$ 和 $x$ 均满足 $\le x$ 这个条件，即都是使 $l$ 更新，所以二分时进行的操作是一样的！也就是说，把这两个数交换后，并不会影响原二分的运行过程。那么交换 $x$ 和 $p_l$ 即可，操作次数为 $1$。 若否，那么由性质可知，交换 $x$ 和 $p_l$ 即可，操作次数为 $1$。 * $p_l > x$。这时我们想想，什么时候才会更新 $l$？当 $p_m \le x$ 的时候，$l$ 会赋值为 $m$。也就是说，如果 $l$ 被更新过，那么 $p_l$ 是一定满足条件 $p_l \le x$ 的。但现在 $p_l > x$，说明 $l$ 并没有被更新过！即二分过程中，只有 $r$ 在更新。那什么时候会更新 $r$？当 $p_m > x$ 的时候。这说明 $x$ 没有作为 $p_m$ 进行比较过，那么由性质可知，交换 $x$ 和 $p_l$ 即可，操作次数为 $1$。 现在观察分类讨论的第 $2$ 种情况中的 $3$ 种状态，发现它们竟然是一样的。那在程序中把它们合并在一起就行了。 注意输出的是交换数字的位置，在读入时记录 $x$ 的出现位置 $pos$ 即可。 ```cpp #include <bits/stdc++.h> #define il inline namespace Fast_IO { template <typename T> il void read(T &x) { x = 0; int f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) x = x * 10 + (ch - 48), ch = getchar(); x = f ? -x : x; } template <typename T, typename ...Args> il void read(T &x, Args& ...args) {read(x), read(args...);} template <typename T> il void write(T x, char c = '\n') { if (x) { if (x < 0)x = -x, putchar('-'); char a[30]; short l; for (l = 0; x; x /= 10) a[l ++] = x % 10 ^ 48; for (l --; l >= 0; l --) putchar(a[l]); } else putchar('0'); putchar(c); } } using namespace Fast_IO; using namespace std; const int Maxn = 200005; int a[Maxn]; signed main() { int T; read(T); while (T --) { int n, x, ans; read(n, x); for (int i = 1; i <= n; i ++) { read(a[i]); if (a[i] == x) ans = i; } int l = 1, r = n + 1; while (r - l > 1) { int mid = (l + r) >> 1; if (a[mid] <= x) l = mid; else r = mid; } if (a[l] == x) puts("0"); else puts("1"), write(l, ' '), write(ans); } return 0; } ```