分析

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

回忆一下

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

不能同时存在。

CPP

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

P14053 [SDCPC 2019] Median 题解

文章操作

分析

实现

相关推荐

评论

P14053 [SDCPC 2019] Median 题解