链接:https://codeforces.com/contest/1443/problem/C
题意:
对于每道菜i,点外卖的话花费a[i],自己去拿的话花费b[i],外卖的时间都是平行的。
问最短多长时间获得所有外卖?
思路:
二分最后答案,维护一个sum为自己取外卖的时间,二分的时候贪心的去考虑,如果a[i]<=b[i],就不管了,如果a[i] > b[i],那么sum+=b[i].
代码:
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5+7; int a[maxn], b[maxn]; signed main() { int t; cin >> t; while(t--){ int n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> b[i]; int l = 1, r = 1e18; while(l < r) { int mid = l + r >> 1; int sum = 0; for(int i = 1; i <= n; i++) { if(a[i] > mid) { sum += b[i]; } } if(sum <= mid) r = mid; else l = mid+1; } cout << l << endl; } }