图片说明
图片说明

  • 题意：
  • 就是个背包的题意，有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;
}

```