题目大意
你需要去n个餐厅取菜,你可以选择自己去取,也可以选择叫外卖,ai表示第i家餐厅
送到你家所需的实际,bi表示自己去第i家餐厅取菜所需时间,已知餐厅在你离开家
时同时送餐,求取到所有菜的最短时间
思路分析
我们先假设所有菜都送外卖过来,按ai大小对送到的时间由大到小排序,针对当前送
到家的最大时间,如果去餐厅取比送外卖时间短,那么显然自己去取更优秀,从大到
小枚举即可,如果在某一道菜时,自己去取的总时间大于送外卖的最大时间,直接输
出即可
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=2e5+10;
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return ret*f;
}
int t;
int n;
int b[maxn];
struct node{
int id;
int v;
}a[maxn];
bool operator < (const node &x,const node & y){
return x.v>y.v;
}
signed main(){
// freopen("a.txt","r",stdin);
t=read();
while(t--){
n=read();
for(int i=1;i<=n;i++){
a[i].v=read();
a[i].id=i;
}
for(int i=1;i<=n;i++){
b[i]=read();
}
sort(a+1,a+1+n);
int add=0;
int fla=0;
for(int i=1;i<=n;i++){
if(add>=a[i].v){
cout<<add<<endl;//add比上一道菜小,比当前大,最大值为add,直接输出
fla=1;
break;
}
if(a[i].v>=b[a[i].id])
add+=b[a[i].id];
else{
cout<<a[i].v<<endl;
fla=1;
break;
}
if(add>=a[i].v){
cout<<a[i].v<<endl;
fla=1;
break;
}
}
if(!fla){
cout<<add<<endl;//优化失败,输出
}
// memset(b,0,sizeof(b));
// memset(a,0,sizeof(a));
}
return 0;
}