[数据结构与算法]背单词的小智 (二分)

D. 背单词的小智

题意

代码

#include<iostream>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
int a[maxn];
ll nums[maxn];
long long c= 0;
ll n,k;
ll maxl = 1e9+10;
int check(ll mid){

    int cnt= 0;
    ll res = 0 ;
    ll d= 0 ;
    for(int i=1;i<=n;i++){
        ll t = a[i]*a[i];
        if(t > mid) return false;
        if(res+t>mid){
            cnt++;
            res = t;
        }
        else{
            res+=t;
        }
    }
    if(cnt>k){
        return false;
    }
    
    if(cnt<=k)
    return true;
}
int main(){ 
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        c+=a[i]*a[i];
    }
    ll l = 1,r= c+1;
    while (l < r){
    	ll mid = (l + r )/2;
    	if (check(mid)) r = mid;    // check()判断mid是否满足性质
    	else l = mid + 1;
    }
    cout<<l<<endl;
    return 0;
}