题面
原题
【题目描述】
西域商人石染典赶着他的十头驴儿，载着葡萄酒、金银器物往来玉门关外，经年累月经营着他的商队生意。从长安到吐鲁番，绵绵五千里，不说坐飞机，乘火车也是相当熬人的旅程，可石染典得靠他的11路公交车完成 （真的抽象啊） 。因此他必须得考虑他携带商品价值的时令性。
石染典有 n 个商品，每个商品有两个属性 ki 和 bi，表示它在时刻 x 的价值为 ki*x + bi，i 是商品序号。
石染典可以选择不超过 m 个商品，使得存在某个整数时刻 t ≥ 0 时，所有物品的总价值大于等于 S。
假设开始时刻是0，给出 S，求 t 的最小值。
【输入格式】
第一行三个整数n, m, S。
接下来n 行，第i 行两个整数ki、bi，表示每件商品的两个属性。
【输出格式】
输出一个整数表示答案。
【输入输出样例】
【数据范围】
对于所有数据，有1 ≤ m ≤ n ≤ 10^6, −10^9 ≤ bi ≤ 10^9, −10^6 ≤ ki ≤ 10^6, 0 ≤ S ≤ 10^18。数据保证有解，且答案不超过10^9。
对于22% 的数据：n ≤ 20；对于另外36% 的数据：n≤ 10^5, 0 ≤ ki ≤ 10^4；对于另外8%的数据：ki ≤ 0；对于另外12% 的数据：n ≤ 10^5；对于另外的其他数据没有特殊约束。
题意概括
有 $n$ 个数，每个数随着时间 $t$ 变化的函数为 $k_{i}t+b_{i}$ ，现要求在某个时刻 $t_{0}$ 选择最多 $m$ 个数，使得这些数的总和大于等于$S$ ，输出 $t_{0}$ 的最小值。
题解
我们发现，对于任意一个选取的集合，其中的数之和都可以表示为关于时间 $t$ 的一次函数。但我们不需要关注所有，只需要关心这些一次函数的最大值。
现在，我们来随便画几条线，用笔描出最大值，记为一个新函数 $g(x)$，你发现了什么？
不管你怎么画，$g(x)$ 只有三种情况：
1.单调递增
2.单调递减
3.先单调递减，再单调递增
为什么会这样呢？很简单，因为组成 $g(x)$ 的每条直线从左到右 $k$ 之一定是不断变大的，否则它就无法代替前一条直线，取得组成 $g(x)$ 的资格。
知道了这一点以后，接下来就好办了。我们只需要先判断一下 $t=0$ 的时候符不符合，若不符合，即 $g(0)<S$，则直接对 $t$ 进行二分即可。为什么可以二分？因为我们刚才已经证明了，$g(x)$ 的单调性只有三种情况。第二种情况与直线 $y=S$ 无交点，即无解，舍去（题面中说了保证有解）；另外两种情况都与 $y=S$ 有一个交点，那么“是否符合条件”是关于 $t$ 单调的，所以可以二分。如果 $g(0)>=S$ ，那么直接输出 $0$ 即可。（虽然经过测试，不判断 $g(0)>=S$ 也可以过，这说明数据有多水）
二分代码示例：
int l=0,r=1e9;//题面中又说答案小于等于1e9
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
现在就是判断符不符合的问题了，也就是check函数。
注意到check的时候我们只需要找出最大的 $m$ 个即可，因此可以 $O(n)$ 地做。做法就是将最大的 $m$ 个放在数列的左边，而这 $m$ 个数内部是否有序不用管，具体是快排的过程中只递归一边。当然也不用你手写，$STL$ 已经给你准备好了：nth_element函数 （STL YYDS）
有人会问：nth_element默认是将前 $m$ 小的数放到数列左边，而我们要的是前 $m$ 大，怎么办？
答：那就不要让它默认！传一个greater<int>()的参数进去即可，和sort里一样。
看代码前，有一个啸细节需要注意：在累加 $k_{i}x+b_{i}$ 时甚至会爆long long。解决方法有两个：
1.使用__int128
2.只要检测到大于 $S$ ，就退出累加，直接让函数返回true。（见代码）
若不注意，即将下面代码中27~32行换成：
for(int i=1;i<=m;i++)
{
if(x[i]>0) ans+=x[i];
}
if(ans>=s) return true;
else return false;
那么会挂19分。
接下来，请食用完整代码：
（代码中itisok函数就是上文中所说的判断是否符合的函数）
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m,s,k[N],b[N],x[N];
inline int read()//快读函数，可以快速读取（输入）
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*w;
}
bool itisok(int mid)
{
for(int i=1;i<=n;i++)
{
x[i]=k[i]*mid+b[i];
}
//sort(x+1,x+n+1,greater<int>()); 用sort会超时，88分
nth_element(x+1,x+m,x+n+1,greater<int>());
int ans=0;
for(int i=1;i<=m;i++)
{
if(x[i]>0) ans+=x[i];
if(ans>=s) return true;
}
return false;
}
signed main()
{
//freopen("merchant.in","r",stdin);
//freopen("merchant.out","w",stdout);
n=read();
m=read();
s=read();
for(int i=1;i<=n;i++)
{
k[i]=read();
b[i]=read();
}
int l=0,r=1e9,ans;
if(itisok(0))
{
cout<<0;
return 0;
}
while(l<=r)
{
int mid=(l+r)>>1;
if(itisok(mid))
{
//cout<<mid<<" ";
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%lld",ans);
}
时间复杂度$O(nlog10^9)$
谁去西域经商是作11路公交车的呀
还有，为什么有些时候商品价值还可以为负数啊！我卖给你我还要给你钱是吧