P4058 [Code+#1] 木材
1:思路:二分月数,然后贪心,就是说要求最小月数,拿每次判断是否到达s长度的时候我们就从大的开始拿。
int l=-1,r=1e18+1;while(l+1<r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid;}
2:记得看数据,开unsigned long long 不然见祖宗
3:ACcode:
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=2e5+10;
int n,s,l,h[N],a[N],c[N];
bool cmp(int i,int j){return i>j;
}
bool check(int x){for(int i=1;i<=n;i++){c[i]=h[i]+x*a[i];}sort(c+1,c+1+n,cmp);int sum=0;for(int i=1;i<=n;i++){if(c[i]>=l){sum+=c[i];if(sum>=s)return true;}else break;}if(sum>=s)return true;return false;
}
void solve() {cin>>n>>s>>l;for(int i=1;i<=n;i++) cin>>h[i];for(int i=1;i<=n;i++) cin>>a[i];int l=-1,r=1e18+1;while(l+1<r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid;}cout<<r<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int tt=1;//cin>>tt;while(tt--) solve();return 0;
}
over~