博客

我们考虑三分 a = 1, b = 1 的书的数量，然后以确定的数量，来挑选 a = 1, b = 0 的书以及 a = 0, b = 1 的书的数量。然后再对剩下的书按时间排序，按时间从小到大挑选，直到数量为m。

至于为什么是三分问题，我的理解是这样：

令 num 为当前 a = 1, b = 1 的书的数量，ans 为正解的 a = 1, b = 1 的书的数量。

当num < ans时，会多拿 a = 1, b = 0 的书以及 a = 0, b = 1 的书。num越小，拿的越多，最终用时就越多。

当num > ans时，会多拿 a = 1, b = 1 的书。num越大，拿的越多，最终用时就越多。

所以该问题是个凹函数，采用整数域的三分解决。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int inf = 2e9 + 1;
int n, m, k, t, a, b, anums = 0, bnums = 0, abnums = 0;

vector<pair<int, int> > ti[4];
vector<pair<int, int> > other;
vector<int> ans;

int cal(int num){
   
    int tol = 0;
    int need = max(0, k - num);                                 // 预防有些时候1，1的数量比k还大
    other.clear();
    if(ti[1].size() < need || ti[2].size() < need) return inf;</