[蓝桥杯]-最大的通过数-CPP-二分查找、前缀和

目录

一、题目描述：

二、整体思路：

三、代码：

---

一、题目描述：

二、整体思路：

1. 首先要知道不是他们同时选择序号一样的关卡通关，而是两人同时进行两个入口闯关。就是说两条通道存在相同关卡编号的的关卡被通关。
2. 由于两人必须按各自通道顺序通关，每通关一次要消耗被通关关卡的水晶数，那么很自然想到用前缀和数组来保存各自的消耗的水晶数。
3. 由于通关关卡数和水晶总数成反比，因此可以枚举所有可能的通关数，通过二分提高查找效率，每次枚举一个可能的通关数都要用一个check函数进行验证。
4. check函数中，输入可能的通关数，输出完成这个通关数所需要的最小的水晶数，那么一个人的通关数x取值范围是0-mid，另一个人的通关数即为mid-x。利用前缀和数组把两个人所消耗的水晶数相加，每次相加都要和上一次结果比较取最小值。
5. 注意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;
}