用时和内存都是最少!!
2024-02-27 17:28:26
发布于:广东
25阅读
1回复
1点赞
#include <iostream>
#include <algorithm>
using namespace std;
struct data{
long long h,p;
};
data a[100005];
long long mina[100005];
int cmp(data x,data y) {
return x.h<y.h;
}
int main() {
int T;
scanf("%d",&T);
while (T--) {
int n,flag=0,L=1;
long long x,sum=0;
scanf("%d %lld",&n,&x);
for (int i=1;i<=n;i++) {
scanf("%lld",&a[i].h);
}
for (int i=1;i<=n;i++) {
scanf("%lld",&a[i].p);
}
sort(a+1,a+1+n,cmp);
mina[n+1]=1e18;
for (int i=n;i>=1;i--) {
mina[i]=min(mina[i+1],a[i].p);
}
while (x>0) {
sum+=x;
int l=L,r=n,ans=1e9;
while (l<=r) {
int mid=(l+r)>>1;
if (a[mid].h>sum) {
ans=min(ans,mid);
r=mid-1;
}else {
l=mid+1;
}
}
if (ans==1e9) {
flag=1;
break;
}
L=ans;
x-=mina[ans];
}
if (flag==1) {
printf("YES\n");
}else {
printf("NO\n");
}
}
return 0;
}
全部评论 1
虽然比赛时没想出来用二分
。。。2024-02-27 来自 广东
0
有帮助,赞一个