首先我们可以证实对于两种食物i,j如果 pi<=pj&&si>=sj 那么j是不会对答案做出贡献的
所以要先筛选出来有用的物品,贪心的过程结束了
笔者最初联想到三分,可以枚举叫外卖的次数,但并不能证明外卖的次数与宅的天数之间是一个单峰函数
随着叫外卖次数的增加,基础的花费(F)在增加,可以使用的钱减少, 同时能够尽量选择价格小的食物, 可以看出这是一个类似于二次函数的东西
然后笔者就莫名其妙的过了,(虽然性质仍然无法理解 QAQ) 如有大神可以证明,欢迎指导
(调了一个多小时最后发现,longlong乘爆了 TAT, 到网上膜拜大神代码习得了新的三分姿势)
1 #define MAXN 210UL 2 #include <cstdio> 3 #include <algorithm> 4 5 using namespace std; 6 7 typedef long long ll; 8 9 ll m, cnt, F, n; 10 11 struct ME { 12 ll p, s; 13 friend bool operator < (ME x, ME y) { 14 return x.s==y.s?x.p<y.p:x.s>y.s; 15 } 16 }pt[MAXN], q[MAXN]; 17 18 ll Get_(ll mid) { 19 if(!mid) return 0; 20 ll ret = 0, now_cost = mid*F; 21 for(int i = 1 ; i <= cnt ; ++ i) { 22 if((q[i].s-q[i-1].s)<=((m-now_cost)/mid)/q[i].p) { 23 now_cost += mid*(q[i].s-q[i-1].s)*q[i].p; 24 ret += mid*(q[i].s-q[i-1].s); 25 } else return ret += (m-now_cost)/q[i].p; 26 } 27 return ret; 28 } 29 30 int main() { 31 scanf("%lld%lld%lld", &m, &F, &n); 32 for(int i = 1 ; i <= n ; ++ i) scanf("%lld%lld", &pt[i].p, &pt[i].s), ++ pt[i].s; 33 sort(pt+1, pt+n+1); 34 q[cnt = 1] = pt[1]; 35 for(int i = 2 ; i <= n ; ++ i) if(pt[i].p<q[cnt].p) q[++ cnt] = pt[i]; 36 reverse(q+1, q+cnt+1); 37 ll l = 1ll, r = m/(F+q[1].p), ans = 0; 38 while(r-l>=3) { 39 ll len = r-l+1; 40 ll mid = l+len/3, midd = l+len*2/3; 41 ll w1 = Get_(mid), w2 = Get_(midd); 42 if(w1>w2) r = midd-1; 43 else l = mid+1; 44 } 45 for(ll i = l ; i <= r ; ++ i) ans = max(ans, Get_(i)); 46 printf("%lld", ans); 47 return 0; 48 }