[SDCPC2023] Fast and Fat题解

LIUYC_C · 2023-08-19 09:53:45 · 题解

题目链接

大体思路：

挺显然的，观察到要最慢的队员最快，即要求最小值的最大值，一眼二分最慢的速度。

考虑怎么 check 答案，即判断在最慢速度的限制下，所有的队员的速度是否都大于这个值，若大于，返回 true，否则返回 false。

观察到还有背起操作，只有速度小于二分的速度的才要被背起，那么大于二分速度的人数小于小于二分速度的人数的话，肯定就背不了那么多人，返回 false 就好，此时考虑贪心，拆完括号后，得到一个队员被背起后的速度变为了 v_{i}+w_{i}-w_{j}，那么我们肯定让速度和体重之和最大的去背体重最大的，排个序就好。

代码实现：

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+10;

struct node{
  int v;
  int w;
}tr[N],h[N];

int w[N];
int m[N];

bool cmp(int a,int b){
  return a>b;
}  

int n;

bool check(int x){
  int ans=0;
  int idx1=0,idx2=0;
  for(int i=1;i<=n;i++){
    if(tr[i].v>=x){
      ans++;
      w[++idx1]=tr[i].w+tr[i].v;
    }
    else{
      m[++idx2]=tr[i].w;
    }
  }
  if(idx1<idx2)return false;
  sort(w+1,w+idx1+1,cmp);
  sort(m+1,m+idx2+1,cmp);
  for(int i=1;i<=idx2;i++){
    if(w[i]-m[i]<x){
      return false;
    }
  }
  return true;
}

void solve(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>tr[i].v>>tr[i].w;
  }

  int l=1,r=1e9;
  while(l<r){
    int mid=l+r+1>>1;
    if(!check(mid))r=mid-1;
    else l=mid;
  }
  cout<<l<<endl;
}

signed main(){
  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  while(t--){
    solve();
  }
  return 0;
}