CF1443C题解
CF1443C题解
- 题目
- 链接
- 字面描述
- 描述
- 输入描述
- 输出描述
- 样例输入1
- 样例输出1
- 思路
- 分析
- 1：二分
- 2：贪心
- 代码实现
题目
链接
http://oi.hdoi.cn/training/8/problem/CF-1443C
字面描述
描述
小 A 刚刚结束考试，他想庆祝一下准备自己做一顿大餐，但是他发现自己还不会做饭，于是只能去点外卖。他在手机上下单了 n 道菜，每一道菜来自不同的餐厅，对于每一种菜，他可以选择让餐厅快递员送，也可以选择自己到店去取。第 i 道菜让餐厅送需要的时间为 a
i
，自己去拿需要的时间为 b
i
。注意自己去取的时候，快递员也可以同时在送。
问他最少需要多久可以把所有的菜都送到家里。
输入描述
第一行包含一个正整数 t （ 1≤t≤2⋅10
5
）表示测试数据的组数。
每组数据的第一行包含一个整数 n （ 1≤n≤2⋅10
5
）表示小 A 想要点的菜数。
第二行包含 n 个整数 a
1
…a
n
( 1≤a
i
≤10
9
) 表示第 i 道菜由快递员送所需要的时间。
第三行包含 n 个整数 b
1
…b
n
( 1≤b
i
≤10
9
) 表示第 i 道菜由自己取所需要的时间。
所有测试数据的 n 总和不超过 2⋅10
5
。
输出描述
对于每个测试输出，输出一个整数，即所有菜取到的最短时间。
样例输入1
4
4
3 7 4 5
2 1 2 4
4
1 2 3 4
3 3 3 3
2
1 2
10 10
2
10 10
1 2
样例输出1
5
3
2
3
思路
分析
若让外卖员送餐，时间花费将是其中时间的最大值
若让自己取餐，时间花费是自己取得时间总和
1：二分
二分最终花费时间mid；
小于mid外卖员送的时间标记为外卖员送
剩下的自己取，时间求和，与mid比较
二分
2：贪心
将外卖员花费时间从小到大排序
求出自取时间后缀和
循环一边求时间取最小值
代码实现
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const int inf=1e9;
int t,n,ans;
int a[maxn],b[maxn];
bool vis[maxn];
inline bool check(int k){
ll cnt=0;
for(int i=1;i<=n;i++)vis[i]=false;
for(int i=1;i<=n;i++){
if(a[i]<=k)vis[i]=true;
}
for(int i=1;i<=n;i++){
if(!vis[i])cnt=(ll)cnt+b[i];
}
if(cnt>k)return false;
return true;
}
int main(){
cin>>t;
while(t--){
ans=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
int l=0,r=inf;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<endl;
}
return 0;
}