目录
一、题目描述:
二、整体思路:
三、代码:
一、题目描述:
二、整体思路:
- 首先要知道不是他们同时选择序号一样的关卡通关,而是两人同时进行两个入口闯关。就是说两条通道存在相同关卡编号的的关卡被通关。
- 由于两人必须按各自通道顺序通关,每通关一次要消耗被通关关卡的水晶数,那么很自然想到用前缀和数组来保存各自的消耗的水晶数。
- 由于通关关卡数和水晶总数成反比,因此可以枚举所有可能的通关数,通过二分提高查找效率,每次枚举一个可能的通关数都要用一个check函数进行验证。
- check函数中,输入可能的通关数,输出完成这个通关数所需要的最小的水晶数,那么一个人的通关数x取值范围是0-mid,另一个人的通关数即为mid-x。利用前缀和数组把两个人所消耗的水晶数相加,每次相加都要和上一次结果比较取最小值。
- 注意long long、二分边界问题。
三、代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=2e5+10;
using ll = long long;
ll k;
int arr_l[N];
int arr_r[N];
ll prevfix_l[N];
ll prevfix_r[N];
ll check(ll mid){//返回要通过mid道关卡一共要多少块紫水晶
ll ans=INT_MAX;
for(int x=0;x<=mid;x++){
if(x<=n && mid-x<=m) ans=min(ans,prevfix_l[x]+prevfix_r[mid-x]);
}
return ans;
}
int main(){
cin>>n>>m>>k;
for(int i = 1;i<=n;i++){
cin>>arr_l[i];
prevfix_l[i]=prevfix_l[i-1]+arr_l[i];
}
for(int i=1;i<=m;i++){
cin>>arr_r[i];
prevfix_r[i]=prevfix_r[i-1]+arr_r[i];
}
ll l=0,r=n+m+10;
while(l+1!=r){
ll mid=(l+r)>>1;//mid是通过的关卡数量
if(check(mid)<=k){
l=mid;
}else{
r=mid;
}
}
cout<<l;
return 0;
}