宅男计划 题解

贪心那一段真的太难受了。

有两个外卖 $i,j$，如果 $p_i\ge p_j$ 且 $s_i \le s_j$，说明 $i$ 这个外卖啥都不如 $j$，直接把 $i$ 踢掉。这时候 $s_i$ 随 $p_i$ 增长而增长了。

我们先考虑如果确定了点外卖次数 $x$ 后怎么计算能活多久。

容易发现这个玩意是个贪心，先从最便宜的外卖开始买，直到每次都买到 $s_i-s_i-1+1$ 个就不买了，因为再买就会过期，还不如不买。然后计算他能活多久。

然后总不可能枚举 $x$ 吧，当我们手动模拟后发现 $x$ 和活的时间呈一个单峰函数，而那个最大值就是我们要求的答案。所以可以三分找单峰函数的最大值。

为啥这个是一个单峰函数，下面有一个感性理解：

• 如果点外卖次数多了，可以多买几个便宜点的，但是外卖费可能会很贵。

• 如果点外卖次数少了，一次必须要点很多份外卖，外卖费又要贵起来。

于是我们要合理控制点外卖的次数。

好了可以用我的题解去洛谷交题解了。

注意要开 __int128。

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define int __int128
using namespace std;
const int N=200+5;
namespace fastio{
	struct reader{
		template<typename T>reader&operator>>(T&x){
			char c=getchar();short f=1;
			while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}
			x=0;while(c>='0'&&c<='9'){
				x=(x<<1)+(x<<3)+(c^48);
				c=getchar();
			}x*=f;return *this;
		}
	}cin;
	struct writer{
		template<typename T>writer&operator<<(T x){
			if (x==-1)return putchar('\n'),*this;
			if (x==-2)return putchar(' '),*this;
			if(x==0)return putchar('0'),*this;
			if(x<0)putchar('-'),x=-x;
			static int sta[45];int top=0;
			while(x)sta[++top]=x%10,x/=10;
			while(top)putchar(sta[top]+'0'),--top;
//			if (x=='\n') putchar(x);
			return*this;
		}
	}cout;
};
#define cin fastio::cin
#define cout fastio::cout
#define endl -1
#define kg -2
struct Node{
	int p,s;
	bool operator < (const Node &a) const {
		return s<=a.s && p>=a.p;
	}
	bool operator == (const Node &a) const{
		return p==a.p && s==a.s;
	}
}a1[N],a[N];
int n,m,f;
int clac(int x){//x为购买外卖次数
	int s=m-f*x,t=0,res=0,d;
	if (s<0) return 0;
	for (int i=1;i<=n;++i){
		d=min(a[i].s-t,s/(a[i].p*x));
		t+=d,s-=d*a[i].p*x,res+=d*x;
		if (t<a[i].s){
			res+=s/a[i].p;
			break;
		}
	}
	return res;
}
signed main(){
	cin >> m >> f >> n;
	for (int i=1;i<=n;++i){
//		scanf("%d%d",&a1[i].p,&a1[i].s);
		cin >> a1[i].p >> a1[i].s;
		++a1[i].s;
	}
	int tot=0;
	bool f=true;
	int ans=0;
	for (int i=1;i<=n;++i){
		f=true;
		for (int j=1;j<=n && f;++j){
			if (i==j) continue;
			if (a1[i]==a1[j] && i<j) f=false;
			if (a1[i]<a1[j]) f=false;
		}
		if (f) a[++tot]=a1[i];
	}
	n=tot;
	sort(a+1,a+n+1,[](const Node &a,const Node &b){return a.s<b.s;});
	int l=1,r=m/(f+a[1].p);
	while (l<r){
		int p=l+(r-l)/3,q=r-(r-l)/3;
		if (p>q) swap(p,q);
		if (clac(p)<clac(q)) l=p+1;
		else r=q-1;
		ans=max(ans,max(clac(p),clac(q)));
//		cout<<l<<kg<<r<<endl;
	}
//	cout<<l<<endl;
	cout<<clac(l)<<endl;
	return 0;
}
//呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜
//呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜
//呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜终于过了