1 solutions
-
0
虎鲸der答案:)
依旧素二分,重点在于check函数中星星开始闪烁时,在不在开始看到天亮的时间段。
知道这个后二分就好写了:)
这题很简单(?#include<bits/stdc++.h> using namespace std; int n; const int M=1e5+2; long long a[M],b[M]; long long l,r,c; int check(long long m){ long long sum=0; for(int i=1;i<=n;i++){ if(b[i]>m)continue; if(b[i]>=l) //普通情况 sum +=(m-b[i])/a[i]+1; else//其他情况 sum+=((m-b[i])/a[i]-(l-1-b[i])/a[i]); if(sum>=c) return 1; } return 0; } signed main(){//和int一样 ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); //快读,可以不写。 cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; cin>>l>>r>>c; long long l1=1,r1=r; long long ans=-1; while(l1<=r1){ long long mid=(r1+l1)/2; if(check(mid)){ r1=mid-1; ans=mid; } else l1=mid+1; } if(ans==-1) cout<<-1; else cout<<ans ; return 0; }
- 1
Information
- ID
- 85
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 9
- Accepted
- 2
- Uploaded By