题目描述
有$n$个物品,第$i$个物品有两个属性$k_i,b_i$,表示它在时刻$x$的价值为$k_i\times x+b_i$。
当前处于时刻$0$,你可以选择不超过$m$个物品,使得存在某个整数时刻$t,t\geqslant 0$,你选择的所有物品的总价值大于等于$S$。
给出$S$,求$t$的最小值。
输入格式
从文件$merchant.in$中读入数据。
第一行三个整数$n,m,S$。
接下来$n$行,第$i$行两个整数$k_i,b_i$。
输出格式
输出到文件$merchant.out$中。
一行一个整数表示答案。
样例
样例输入1:
3 2 100
3 9
-2 50
4 1
样例输出1:
13
样例输入2:
3 2 100
-1 49
-2 50
1 -998244353
样例输出2:
998244453
数据范围与提示
样例$1$解释:
选择$1,3$号物品。
样例$2$解释:
选择$3$号物品。
数据范围:
对于所有数据,有$1\leqslant m\leqslant n\leqslant 10^6,−10^9\leqslant b_i\leqslant 10^9,−10^6\leqslant k_i\leqslant 10^6,0\leqslant S\leqslant 10^{18}$。
数据保证有解,且答案不超过$10^9$。
$\bullet Subtask1(22\%)$,$n\leqslant 20$。
$\bullet Subtask2(36\%)$,$n\leqslant 10^5,0\leqslant k_i\leqslant 10^4$。
$\bullet Subtask3(8\%)$,$k_i\leqslant 0$。
$\bullet Subtask4(12\%)$,$n\leqslant 10^5$。
$\bullet Subtask5(22\%)$,没有特殊的约束。
题解
显然我们只会在最后一天将我们想买的这$m$件物品都买下。
所以答案满足单调性,二分天数即可。
但是坐观数据范围,我们显然不能在$judge$的时候用$sort$,否则最后$22$分跑不过去,所以可以用$nth\text{_}element$减掉一个$\log n$。
时间复杂度:$\Theta(n\log 10^9)$。
期望得分:$100$分。
实际得分:$100$分。
代码时刻
#include<bits/stdc++.h> using namespace std; int n,m; long long S; pair<int,int> e[1000001]; long long flag[1000001]; bool judge(int x) { for(int i=1;i<=n;i++) flag[i]=1LL*e[i].first*x+e[i].second; nth_element(flag+1,flag+n-m+1,flag+n+1); long long res=0; for(int i=n;i>n-m;i--) { if(flag[i]>0)res+=flag[i]; if(res>=S)return 1; } return 0; } int main() { scanf("%d%d%lld",&n,&m,&S); long long sum=0; for(int i=1;i<=n;i++) { scanf("%d%d",&e[i].first,&e[i].second); sum+=e[i].second; } if(sum>=S) { puts("0"); return 0; } int lft=0,rht=1000000000,ans=1000000000; while(lft<=rht) { int mid=(lft+rht)>>1; if(judge(mid)){ans=mid;rht=mid-1;} else lft=mid+1; } printf("%d\n",ans); return 0; }
rp++