2 solutions

  • 1
    @ 2022-6-6 22:13:55

    凡是二分题,难点总是在找check,所以只要能找到check,题就很容易了

    #include<iostream>
    using namespace std;
    #define MAX 1000000007
    #define N 100007
    
    int n,m,s;
    int a[N];
    
    int check(int x){
    	int now=0,cns=1;
    	for(int i=1;i<=n;i++){
    		if(now+a[i]<=x)now+=a[i];
    		else {
    			cns++;
    			i--;
    			if(cns>m)return false;
    			now=0;
    		}
    	}
    	return true;
    }
    
    int search(int l,int r){
    	int mid;
    	while(l<=r){
    		mid=(l+r+1)>>1;
    		if(check(mid))r=mid-1;
    		else l=mid+1;
    	}
    	return r+1;
    }
    
    int main(){
    	ios::sync_with_stdio(false);
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		s+=a[i];
    	}
    	
    	int ans=search(0,s);
    	cout<<ans;
    	return 0;
    	
    }
    

    Information

    ID
    168
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    8
    Tags
    # Submissions
    108
    Accepted
    15
    Uploaded By