题解：CF2168B Locate

· · 题解

题意

挂羊头卖狗肉的通信题，通信只是个形式，实际上就是一个常见的区间最值交互。给你一个长为 n 的排列，第一个人先看然后给第二个一个布尔值，第二个人不知道排列但可以询问一个区间，交互库返回该区间的极差，对多查询 30 次，你要找到排列中 n 的位置。

分析

通信题的做法我不再解释了，不会的去看 P12509，具体讲讲如何询问，以及布尔值应该怎么决策。

看到 30 次想到二分，根据数据范围掂量估计是两次查询缩为原来的一半。那么我们思考对于一个区间查询会返回什么呢？

第一种：ans=n-1 即 1 和 n 都在该区间内。

第二种：ans<n-1 即 并非 1 和 n 都在该区间内。

若为第一种，则直接将二分的范围缩小，若为第二种，则说明 n 和 1 要分离了。

根据经验，像 1 和 n 这种极值在极值问题中具有相似性，想起前面的布尔值，可以想到用布尔值表示 n 和 1 的先后关系。

分离后，问题更容易解决了，现在问题转换为已知 1 和 n 分别在两块不交的区间中。因此每次询问可以询问 n 所在区间的一半和 1 所在区间的并集，若返回值为 n-1 则说明 n 只能在选中这一半，否则则只能在另一半。

然后就解决了。

代码：

#include <bits/stdc++.h>
// #define int long long
using namespace std;
void sol1()
{
  int _;
  cin >> _;
  while (_ --)
  {
    int n;
    cin >> n;
    int n1 = -1, nn = -1;
    for (int i = 1; i <= n; i ++)
    {
      int x;
      cin >> x;
      if (x == 1)
        n1 = i;
      if (x == n)
        nn = i;
    }
    cout << (n1 < nn) << endl;
  }
}
void sol2()
{
  int _;
  cin >> _;
  while (_ --)
  {
    int n, x;
    cin >> n >> x;
    int l = 1, r = n;
    while (l < r)
    {
      int mid = (l + r) >> 1, r1, r2;
      printf("? %d %d", l, mid);
      cout << endl;
      cin >> r1;
      printf("? %d %d", mid + 1, r);
      cout << endl;
      cin >> r2;
      if (r1 == n - 1)
      {
        r = mid;
        continue;
      }
      if (r2 == n - 1)
      {
        l = mid + 1;
        continue;
      }
      if (x)
      {
        l = mid + 1;
        break;
      }
      else
      {
        r = mid;
        break;
      }
    }
    while (l < r)
    {
      int mid = (l + r) >> 1, ret;
      if (x)
        printf("? 1 %d", mid), cout << endl;
      else
        printf("? %d %d", mid + 1, n), cout << endl;
      cin >> ret;
      if (ret == n - 1)
        if (x)
          r = mid;
        else
          l = mid + 1;
      else
        if (x)
          l = mid + 1;
        else
          r = mid;
    }
    printf("! %d", l), cout << endl;
  }
}
signed main()
{
  // cin.tie(0)->sync_with_stdio(0);
  string s;
  cin >> s;
  if (s == "first")
    sol1();
  else
    sol2();
  return 0;
}