题目链接:
闲扯
考场上怕T2正解写挂其他两题没管只打了暴力,晚上发现这题思维挺妙的
同时想吐槽出题人似乎热衷卡常…我的巨大常数现在显露无疑QAQ
分析
这道题yy出了一个似乎比solution更好理解的解法,一开始有$n$条一次函数,就有$2^n$种函数集合,显然每个集合也是一个一次函数$T_i(x)=k_i x+b_i$
我们把这个集合分成两种$k_i<=0$和$k_i>0$,显然如果答案最后最大值的函数集合是第一种,那么显然肯定是在$x=0$取到的
所以我们单独把$x=0$拎出来考虑就可以不考虑第一种函数集合的贡献了
对于第二种$k_i>0$的函数集合,应该很容易发现$max(T_i(x))$是单调递增的的图像,可以二分找到答案要求的点
然后这题就做完了
对于0的处理其实就是把$b_i$最大且大于0的拿出来看看是否大于等于S就好了,虽然最后这样的函数集合不一定是第一种$k_i<=0$但是一定考虑进去了
二分的时候也是贪心把该点的处于前$m$大且大于0的单个一次函数值加起来判断一下就好了
这里有个骚操作nth_ment(l,pos,r,cmp),表示将容器中$[l,r)$种第pos个位置的元素变成第$pos$大/小(视cmp函数决定)，同时pos前都是大/小于第pos大/小的元素,pos后类似
代码
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
49
50
51
52
53
54
55
56
| #include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <queue>
#include <vector>
#define ll long long
#define ri register int
using std::min;
using std::max;
using std::nth_element;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=nc()))ne=c=='-';
x=c-48;
while(isdigit(c=nc()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=1000005;
const int inf=0x7fffffff;
ll v[maxn],ki[maxn],bi[maxn];
int n,m;ll s;
bool ok(int x){
for(ri i=1;i<=n;i++)v[i]=ki[i]*x+bi[i];
nth_element(v+1,v+m,v+n+1,std::greater<ll>());
ll sum=0;
if(sum>=s)return 1;
for(ri i=1;i<=m;i++){
if(v[i]>0)sum+=v[i];
if(sum>=s)return 1;
}
return 0;
}
int main(){
freopen("merchant.in","r",stdin);
freopen("merchant.out","w",stdout);
read(n),read(m),read(s);
for(ri i=1;i<=n;i++){
read(ki[i]),read(bi[i]);
}
if(ok(0)){puts("0");exit(0);}
int L=1,R=1e9,ans;
while(L<=R){
int mid=(L+R)>>1;
if(ok(mid))ans=mid-1,R=mid-1;
else L=mid+1;
}
printf("%d\n",ans+1);
return 0;
}
|