思维题——牛客多校第六场D

这题的不能用二分做，因为不满足单调性的

可以用multiset做

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
multiset<int>s;
multiset<int>::iterator it;
int a[maxn],T,N,K,C;
bool check(int Mid)
{
    s.clear(); int tk=K;
    rep(i,1,N) s.insert(a[i]);
    while(!s.empty()&&tk--){
        int x=Mid;
        while(x){
           it=s.upper_bound(x);
           if(it==s.begin()) break;
           it--;
           x-=*it;
           s.erase(it);
           //cout<<x<<" "<<endl;
        }
       // cout<<"A"<<endl;
    }
    if(!s.empty()) return false;
    return true;
}
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&K);
        int L=1,R=1000000000,Mid,ans,sum=0;
        rep(i,1,N) scanf("%d",&a[i]),L=max(L,a[i]),sum+=a[i];
        L=max(L,sum/K);
        rep(i,L,R) {
            if(check(i)) {
                ans=i; break;
            }
        }
        printf("Case #%d: %d
",++C,ans);
    }
    return 0;
}