题面:
Azone 每次出发前，会搬若干件总重不超过 w 的物品上车：出发前，车是空载的，Azone 会选择能搬上车的家具中最重的一件放上车，然后在剩下的家具中继续选择一件能被搬走的最重的上车，持续装车，直至剩下的家具都塞不上车。
Azone 希望在运送次数不超过 R 的情况下完成转场，求 Azone 最少需要购置价值多少的车。
二分绝世好题。
- 首先看到最少这种字眼想到的肯定是二分，但是他提供的策略十分鬼畜导致$check$函数就很不好写。
经思考（题解），发现用集合很好维护，于是调用$multiset$，存储所有物品的价值，每次upper_bound找最小满足的物品，直至剩余空间连最小都放不下为止。
结果发现可能会出现$Mid$极小导致check函数一直卡着删不掉的问题，还要加一个特判。。
想法很简单，实现很困难，首先要调用$iterator$迭代器啥的进行模拟，触到了一定知识禁区，一个小细节没注意：
这两种情况还是不一样的，但具体为啥还是不清楚，姑且死记硬背吧。。
$vector$排序再$bound(a.begin,a.end)$，$set$直接$s.bound()$，别问我为啥。。
$UPDATE:$貌似是因为$vector$支持随机寻址，可以快速知道某个地址的元素大小啥的。。。
- 交了发现没A掉，但是check没写错了啊！！？
发现不具有单调性，原因是贪心策略导致了方案变劣了。。这谁想得到啊。。
无奈，但是二分整体思路是对的，我们可以发现，
当$W_0$满足时，$W_0+max_{w_i}$也一定满足条件，因为白白多出来一个位置嘛。
于是我们就将当前二分答案倒推一个$max_{wi}$，硬核判断是否满足条件并更新，一定能搜到正解。
这个考试真的推不出来，只是提供一个想法：
当函数不完全满足单调性的时候，可以考虑最小值与单调性部分的最小值有何关系然后硬核判断。
就这样了，放丑陋代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48//Azone 会选择能搬上车的家具中最重的一件放上车,
//然后在剩下的家具中继续选择一件能被搬走的最重的上车
//过程可用multiset维护
using namespace std;
int n,r,w[3000],maxw,sw;
multiset<int> s;
bool check(int x)
{
int now=0,cnt=0; s.clear();
for (int i=1;i<=n;i++) s.insert(w[i]);
sort(s.begin(),s.end());
while (!s.empty())
{
while (!s.empty()&&x-now>=(*s.begin())){
//最小的都塞不进了。。
multiset<int> :: iterator
it=s.upper_bound(x-now);
//迭代器upper存的是大于的，--
it--; now+=(*it); s.erase(it);
}
cnt++; now=0;
if (cnt>r) return 0;
//防止爆栈
}
return (cnt<=r);
}
int main()
{
cin>>n>>r;
for (int i=1;i<=n;i++) cin>>w[i],sw+=w[i];
int l=0,r=sw,mid=0,ans=0;
while (l<r)
{
mid=(l+r)/2;
if (check(mid)) ans=r=mid;
else l=mid+1;
}
for (int i=r;i>max(1,r-2000);i--) if (check(i)) ans=i;
//不具有单调性！！咋办！！
//但是答案取值范围不超过wi，暴力枚举即可
cout<<ans<<endl;
return 0;
}