题解：P14421 [JOISC 2014] 拉面比较 / Ramen

· · 题解

给定一个长为 N\left(N\leqslant 400\right) 的排列，在 600 次询问内找到最大值和最小值的位置。

Algo 1

首先可以直接排序，需要的询问次数 \Theta\left(n\log n\right)。

可以通过第一个测试点。

Algo 2

其次我们知道对于一个长为 N 的序列，可以在 N-1 次比较中找到最大值或最小值。

询问次数为 2N-3，可以通过第二个测试点。

Algo 3

首先把只有一个的情况判掉。

将序列中的数两两分组，每组选出较大值和较小值。

然后从较大值中选出最大值，从较小值中选出最小值。

如果序列中数的个数是奇数，可以把最后一个数与较小值（或最大值）集合中的某个数比较，确定这个数的集合。

询问的次数是 \dfrac{3n}{2}-O(1) 的。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;

int Compare(int X, int Y);
void Answer(int X, int Y);

void Ramen(int N) {
  if (N == 1)
    return Answer(0, 0), void();

  vector<size_t> bigger, smaller;
  for (size_t i = 0; i < N; i += 2) {
    if (i + 1 == N) {
      if (Compare(i, bigger.front()) > 0)
        bigger.front() = i;
      else
        smaller.push_back(i);
    } else {
      if (Compare(i, i + 1) > 0)
        bigger.push_back(i), smaller.push_back(i + 1);
      else
        bigger.push_back(i + 1), smaller.push_back(i);
    }
  }

  size_t biggest = bigger.front();
  for (size_t i = 1; i < bigger.size(); ++i)
    if (Compare(bigger[i], biggest) > 0)
      biggest = bigger[i];

  size_t smallest = smaller.front();
  for (size_t i = 1; i < smaller.size(); ++i)
    if (Compare(smaller[i], smallest) < 0)
      smallest = smaller[i];
  Answer(smallest, biggest);
}

#ifndef ONLINE_JUDGE

int Compare(int X, int Y) { return X > Y ? 1 : -1; }
void Answer(int X, int Y) { cout << X << " " << Y << endl; }

int main() {
  size_t N;
  cin >> N;
  Ramen(N);
  return 0;
}

#endif

:::

话说有没有人会写这题的非自适应交互库啊。