CF1945E 解题报告

· · 题解

思路：分类讨论。

先要想到一个性质：若 x 在二分过程中没有作为 p_m 进行比较，则二分结束后将 x 与 p_l 交换，并不会影响原来二分的运行过程。

  1. 二分结束后 p_l = x。

    此时显然不用交换，已经满足题意。输出 0 即可。

  2. 二分结束后 p_l \neq x。

    • 若是，那么当 $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$。

现在观察分类讨论的第 2 种情况中的 3 种状态，发现它们竟然是一样的。那在程序中把它们合并在一起就行了。

注意输出的是交换数字的位置，在读入时记录 x 的出现位置 pos 即可。

#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;
}