該題數據量較大，根據題目答案最大2*10^9，可以通過二分法查找最大做的蛋糕數，用魔法素材把每個材料補充到二分的值需要的素材數，判斷總共需要的素材數和k的大小關系進行二分

#include<iostream>using namespace std;typedef long long ll;//int數據會溢出改用long longconst ll maxn = 2e9+5; ll a[100005],b[100005]; ll n,k;ll search(ll l,ll r){while( l <= r){ll mid = l + r >> 1;ll sum = 0;//sum表示需要的素材數for( ll i = 0 ; i < n ; ++i ){//如果材料不足就補充if(a[i]*mid > b[i]){sum = sum + a[i]*mid - b[i];}//需要素材量超出擁有魔法材料量跳出if( sum > k ){break;}}//需要素材數和擁有魔法素材數相同直接輸出答案if( sum == k ){return mid;}//需要素材數比擁有魔法素材數小，說明mid小或者mid是答案但魔法材料溢出 //如果mid是答案，l將不會改變最后輸出l-1即可else if(sum < k){l = mid + 1;}//需要素材數比擁有魔法素材數大，說明mid大else{r = mid - 1;}}return l-1; }int main(){cin >> n >> k;for( ll i = 0 ; i < n ; ++i ){cin >> a[i];}for( ll i = 0 ; i < n ; ++i ){cin >> b[i];}cout << search(0,maxn) << endl;return 0; }

總結

以上是生活随笔為你收集整理的E - Magic Powder - 2(二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。