蓝桥杯倒计时 41天 - 二分答案-最大通过数-妮妮的月饼工厂

最大通过数

思路：假设左边能通过 x 关，右边能通过 y 关，x∈[0,n]，通过二分，在前缀和中枚举右边通过的关卡数，保存 x+y 的最大值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;int main( ){static_cast<void>(ios::sync_with_stdio(0)),static_cast<void>(cin.tie(0)),cout.tie(0);cin>>n>>m>>k;vector<ll>a(n+1);vector<ll>b(m+1);for(int i=1;i<=n;i++){cin>>a[i];a[i]+=a[i-1];}for(int i=1;i<=m;i++){cin>>b[i];b[i]+=b[i-1];}ll res = 0;for(int i=0;i<=n;i++){if(a[i]>k)break;ll temp =upper_bound(b.begin(), b.end(), k-a[i])-b.begin()-1;res = max(res,temp+i);}cout<<res<<'\n';return 0;
}

妮妮的月饼工厂

思路：假设高度为 x，由于高度越高月饼数越少呈现单调性，所以可以用二分来进行枚举。高度范围是 1-1e9 要开 longlong，就用所有材料是否能做k 个高度为 x 的月饼来进行判断。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
const int N = 1e5+10;
ll a[N];bool check(ll x){ll res = 0;for(int i=1;i<=n;i++){res += a[i]/x;}return res>=k;
}int main( ){cin>>n>>k;ll sum = 0;for(int i=1;i<=n;i++){cin>>a[i],sum+=a[i];}ll l=0,r=1e9;while(l<r){ll mid = (l+r+1)>>1;if(check(mid))l = mid;else r=mid-1;}if(sum<k)cout<<-1<<endl;else cout<<r<<'\n';return 0;
}