1班专用
2024-02-16 17:19:32
发布于：浙江
21阅读
0回复
0点赞
T7
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005];
bool sum(int x){
long long s=0;
for( int i=1;i<=n;i++){
s+=max(0,a[i]-x);
}
return s>=m;
}
int main(){
int l=0,r=1e9,ans;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
while (l<=r){
int mid=(l+r)>>1;
if(sum(mid)){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
cout<<ans;
return 0;
}
T8
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],tmp[3];
bool sum(int x){
int cnt=1;
int lox=0;
for(int i=0;i<n;i++){
if((lox+a[i])>x){
++cnt;
lox=a[i];
}
else{
lox+=a[i];
}
}
return cnt<=m;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>tmp[2];
if(tmp[2]>tmp[1]) tmp[1]=tmp[2];
a[i]=tmp[2];
}
int l=tmp[1],r=1e9,ans;
while (l<=r){
int mid=(l+r)>>1;
if(sum(mid)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
T9
#include<bits/stdc++.h>
using namespace std;
int k,n,m;
int pos[50005];
bool check(int mid){
int ans=0,st=0;
for(int i=1;i<=n;++i)
if(pos[i]-st<mid)
ans=ans+1;
else st=pos[i];
return ans<=m;
}
int main(){
cin>>k>>n>>m;
for(int i=1;i<=n;++i)cin>>pos[i];
int l=0,r=k,mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid-1;
}
if(!check(l))l-=1;
cout<<l;
return 0;
}
有帮助，赞一个