牛客多校第六场 D

• 题意：
• 就是个背包的题意，有n个物体和k个背包，输出最小的背包体积装下所有的物体，
• 不过装物体有个定义，要求先从大的装，直到装不下为止。
• 题解：
• 二分能做，但是这题二分没有唯一解啊！
• 题解这么说的:
• 15 5
• 39 39 39 39 39 60 60 60 60 60 100 100 100 100 100
• 199 为一个合法的答案，但 200 不是，201 也不是
• 二分找最优解没法做
• 但是可以二分找局部解，然后枚举就行了。
• 这里我看了大佬的代码，也是过了，multiset果然好用啊，赶紧记一下。
• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define ll long long
  int n,k;
  int a[1010];
  int solve(int x)
  {
    int cnt = 0;
    multiset<int> s(a,a+n);
    multiset<int>::iterator it;
    while(1)
    {
        if(++cnt > k)
            return 0;
        int rem = x;
        while(s.size() && rem >= *s.begin())
        {
            it = prev(s.upper_bound(rem));
            //cout<<s.size()<<" "<<*it<<endl;
            rem -= *it;
            s.erase(it);
        }
        if(s.empty())
            return 1;
    }
  }
  int main()
  {
    int t,cas = 0;
    cin>>t;
    while(t--)
    {
        int maxx = 0,sum = 0;
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            if(a[i] > maxx)
                maxx = a[i];
            sum += a[i];
        }
        maxx = max(maxx,sum/k);
        while(!solve(maxx)){
            maxx++;
        }
        printf("Case #%d: %d\n",++cas,maxx);
    }
    return 0;
  }
  

```