[数据结构与算法]CF1443C题解

题目

链接

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;
}