html网页模板网站,作风建设网站,天河区建设和水务局网站,小程序怎么做出来的最大通过数 思路#xff1a;假设左边能通过 x 关#xff0c;右边能通过 y 关#xff0c;x∈[0,n]#xff0c;通过二分#xff0c;在前缀和中枚举右边通过的关卡数#xff0c;保存 xy 的最大值。
#includebits/stdc.h
using namespace std;
typedef long long ll…最大通过数 思路假设左边能通过 x 关右边能通过 y 关x∈[0,n]通过二分在前缀和中枚举右边通过的关卡数保存 xy 的最大值。
#includebits/stdc.h
using namespace std;
typedef long long ll;
ll n,m,k;int main( ){static_castvoid(ios::sync_with_stdio(0)),static_castvoid(cin.tie(0)),cout.tie(0);cinnmk;vectorlla(n1);vectorllb(m1);for(int i1;in;i){cina[i];a[i]a[i-1];}for(int i1;im;i){cinb[i];b[i]b[i-1];}ll res 0;for(int i0;in;i){if(a[i]k)break;ll temp upper_bound(b.begin(), b.end(), k-a[i])-b.begin()-1;res max(res,tempi);}coutres\n;return 0;
}妮妮的月饼工厂 思路假设高度为 x由于高度越高月饼数越少呈现单调性所以可以用二分来进行枚举。高度范围是 1-1e9 要开 longlong就用所有材料是否能做k 个高度为 x 的月饼来进行判断。
#includebits/stdc.h
using namespace std;
typedef long long ll;
int n;
ll k;
const int N 1e510;
ll a[N];bool check(ll x){ll res 0;for(int i1;in;i){res a[i]/x;}return resk;
}int main( ){cinnk;ll sum 0;for(int i1;in;i){cina[i],suma[i];}ll l0,r1e9;while(lr){ll mid (lr1)1;if(check(mid))l mid;else rmid-1;}if(sumk)cout-1endl;else coutr\n;return 0;
}
