CF1705A Mark the Photographer 题解

· · 题解

简单贪心题。贪心结论的证明参考了 CF 官方题解。

首先我们将数组 h 从小到大排序，如果可以安排，那么这个数组一定满足以下条件：

为什么是这样的呢？

我们选取一个 i(1\le i\le n)，对于区间 [h_i,h_{i+n}]，共有 n+1 个身高。这 n+1 个人需要分配到 n 列上去，根据鸽巢原理，必有至少 2 人分到同一列。区间中身高最大的差值显然为 h_{i+n}-h_i，为保证可以安排，我们将 i 和 i+n 两人分配在同一列。因为每一列都要满足身高差大于等于 x，所以我们只要判断 h_{i+n}-h_i 是否大于等于 x 即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,k; cin>>n>>k;
    vector<int> a(n<<1);
    for(auto &i:a)cin>>i;
    sort(a.begin(),a.end());
    bool f=true;
    for(int i=0;i<n;i++)
      if(a[i+n]-a[i]<k){f=false; break;}
    cout<<(f?"YES\n":"NO\n");
  }
  return 0;
}