题解 CF1705A【Mark the Photographer】

2022-07-18 14:52:57


题意

有 $2n$ 个小朋友,身高分别是 $a_{1 \sim 2n}$。问能否将这些小朋友排成两排,每排 $n$ 人,并使得第二排的所有小朋友,身高都至少比其前面的一位小朋友高 $x$?

分析

直接贪心。排序后,判断是否满足 $\forall i \leq n$,$a_{i+n} \geq a_i + x$。

代码

void solution() {
  int n, x;
  read(n, x);
  std::vector<int> a(2 * n + 1);
  for (int i = 1; i <= 2 * n; ++i) read(a[i]);
  std::sort(a.begin() + 1, a.end());
  std::vector<int> A, B;
  for (int i = 1; i <= n; ++i) A.push_back(a[i]);
  for (int i = n + 1; i <= 2 * n; ++i) B.push_back(a[i]);
  for (int i = 0; i < n; ++i)
    if (B[i] - A[i] < x) return void(std::cout << "NO\n");
  std::cout << "YES\n";
}