P14053 [SDCPC 2019] Median 题解

imnotcfz · 2025-09-24 21:41:35 · 题解

分析

题意很明确，这里不多赘述，但我们还是——

回忆一下 n 个元素（n 为奇数）的中位数的定义：将这些元素排序后，中位数是第 \lceil\frac{n}{2}\rceil 大的元素。

也就是说小于和大于中位数的数各有 \lfloor\frac{n}{2}\rfloor 个，两个条件缺一不可，因此我们可以从这一点入手，找出每个数比他大和比他小的数的个数，就能判断一个数是否可能成为中位数。

既然题目中给出了一些大小关系，我们就可以建图——令 u 到 v 的有向边表示 u 的数值大于 v。由于 n 最多只到 99，即最大运算量约为 2\times10^7，所以我们可以直接用 Floyd 算法求出更多的大小关系。

实现

Talk is cheap, show me the code!

需要注意的是 i>j 和 j>i 不能同时存在。

#include <cstring>
#include <iostream>

using namespace std;

int T, n, m;
bool dis[105][105];

int main() {
  cin >> T;
  while (T--) {
    // 多测不清空，小心见祖宗
    memset(dis, 0, sizeof(dis));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
      static int u, v;
      cin >> u >> v;
      // 连边，表示 u 的数值大于 v
      dis[u][v] = true;
    }
    // Floyd 算法
    // 若 a > b 且 b > c，则 a > c
    // 据此对已知的关系进行扩展
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          dis[i][j] |= dis[i][k] & dis[k][j];
    // 注意特判：i > j 和 j > i 不能同时存在
    // 没错，题目只说使得所有大小关系都成立，没说大小关系有没有错
    bool flag = 0;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (dis[i][j] && dis[j][i]) {
          flag = 1;
          break;
        }
    // 全部不成立
    if (flag) {
      for (int i = 1; i <= n; i++) {
        cout << 0;
      }
      cout << endl;
      continue;
    }
    // 计算每个数比他大和比他小的数的个数
    for (int i = 1; i <= n; i++) {
      int greater = 0, less = 0;
      for (int j = 1; j <= n; j++) {
        greater += dis[i][j];
        less += dis[j][i];
      }
      if (greater <= n / 2 && less <= n / 2)
        cout << 1;
      else
        cout << 0;
    }
    cout << endl;
  }
  return 0;
}