Merchant
有n个物品，第i个物品有两个属性ki , bi，表示它在时刻x的价值为ki × x + bi . 当前处于时刻0，你可以选择不超过m个物品，使得存在某个整数时刻t, t ≥ 0，你选择的 所有物品的总价值大于等于S. 给出S，求t的最小值。
很容易想到几个物品加起来的时候，价值是一个一次函数（合并同类项）
然后画一下图可以发现（然而我考试时并没有发现），在同一个x坐标下对应一个最大值，这个最大值是先减后增的。
所以我们可以先判断一下0时刻，如果可以就输出0，不然就二分
每一次判断的时候算出此时的价值，然后用一个骚操作nth_element， 可以求出前m个最大的，复杂度O（n）
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 1e6 + 10;
int k[MAXN], b[MAXN], n, m;
ll c[MAXN], s;bool check(int t)
{ll sum = 0;REP(i, 0, n) c[i] = 1ll * k[i] * t + b[i];nth_element(c, c + m, c + n, greater<ll>()); //从大到小 REP(i, 0, m) if((sum += c[i]) >= s) //注意可能后面的值为负，所以不一定全部加完才最大 return true;return false;
}int main()
{scanf("%d%d%lld", &n, &m, &s);REP(i, 0, n) scanf("%d%d", &k[i], &b[i]);if(check(0)) { puts("0"); return 0; }int l = 0, r = 1e9 + 1;while(l + 1 < r){int m = (l + r) >> 1;if(check(m)) r = m;else l = m;}printf("%d\n", r);return 0;
}