思路
简单题,设函数 \(f_i\) 表示当时间为 \(i\) 时是否能够收拾好所有玩具,则 \(f_i\) 显然是单调的。
所以我们可以考虑二分。
设我们当前二分到 \(x\),我们先把 \(x\) 数组按从小到大排序,\(y\) 数组按从大到小排序。
我们先扫 \(x\) 数组,假设我们当前扫到了 \(x_i\),\(1\) 至 \(j\) 的玩具可以被 \(i\) 安放,则,贪心的想,这些玩具对于 \(x\) 数组的意义是相同的,但是这些玩具的 \(s\) 值是不同的,为了尽可能存在答案,我们需要尽量给遍历 \(y\) 数组时留下尽可能小的 \(s\) 值,所以我们选取最大的 \(x\) 个 \(s\) 值删掉。
接下来扫 \(y\) 数组,每次都尽可能删去值,若最后被删空,则成立,否则不成立。
代码
#include<bits/stdc++.h>
using namespace std;
int const N=1e6+10;
int x[N],y[N],w[N],s[N],n,m,t;
struct node{int w,s;}a[N];
inline bool cmp(node x,node y){return x.w<y.w;}
inline bool check(int lim){
priority_queue<int>q;
int r=0;
for (int i=1;i<=n;++i){
while (a[r+1].w<=x[i] && r+1<=t) q.push(a[++r].s);
int xx=lim;
while (!q.empty() && xx--) q.pop();
}
while (r<t) q.push(a[++r].s);
for (int i=1;i<=m;++i){
if (q.empty()) break;
if (q.top()>y[i]) return 0;
int xx=lim;
while (!q.empty() && xx--) q.pop();
}
if (!q.empty()) return 0;
return 1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>t;
for (int i=1;i<=n;++i) cin>>x[i],--x[i];sort(x+1,x+n+1);
for (int i=1;i<=m;++i) cin>>y[i],--y[i];sort(y+1,y+m+1);reverse(y+1,y+m+1);
for (int i=1;i<=t;++i) cin>>a[i].w>>a[i].s;sort(a+1,a+t+1,cmp);
int l=0,r=1e9;
while (l<r){
int mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
}
if (l==1e9) l=-1;
cout<<l<<'\n';
return 0;
}
标签:sort,return,IOI2013,机器人,robots,mid,int,数组,--
From: https://www.cnblogs.com/tx-lcy/p/16799733.html