一号代码,样例正确:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, sum, limit;
int h[200005], a[200005];
bool check(int mid){
int all=0;
priority_queue<int> q;
int t[200005];
for(int i=1;i<=n;i++) t[i]=h[i]+mid*a[i], q.push(t[i]);
if(q.top()<limit) return 0;
while(q.top()>=limit && q.size()){
all+=q.top();
q.pop();
}
while(q.size()) q.pop();
if(all<sum) return 0;
return 1;
}
signed main(){
cin>>n>>sum>>limit;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++) cin>>a[i];
int l=0, r=1e18, mid, ans;
while(l<=r){
mid=(l+r)/2;
if(check(mid)) ans=mid, r=mid-1;
else l=mid+1;
}
cout<<ans;
return 0;
}
二号代码,样例奇葩:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, sum, limit;
int h[200005], a[200005];
bool check(int mid){
int all=0;
priority_queue<int> q;
int t[200005];
for(int i=1;i<=n;i++) t[i]=h[i]+mid*a[i], q.push(t[i]);
if(q.top()<limit) return 0;
while(q.top()>=limit && q.size()){
all+=q.top();
q.pop();
}
while(q.size()) q.pop();
if(all<sum) return 0;
return 1;
}
signed main(){
cin>>n>>sum>>limit;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++) cin>>a[i];
int l=0, r=LONG_LONG_MAX, mid, ans;
while(l<=r){
mid=(l+r)/2;
if(check(mid)) ans=mid, r=mid-1;
else l=mid+1;
}
cout<<ans;
return 0;
}
除了r一个1e18和一个LONG_LONG_MAX以外,没了!!!
答案却不一样!!!