bzoj 3874 宅男计划

Posted on | Views:

三分 + 贪心.

乍一看有点像网络流,但天数太大了,没法处理.

先将那些没用的食物扔掉,即,若存在 $i,j$ 满足 $S_i\le S_j,P_i\ge P_j$ ,则 $i$ 这种食物就可以扔掉了.

考虑将外卖小哥来的次数记为 $x​$ ,则在最优策略下,能宅的时间 $f(x)​$ 是一个关于 $x​$ 的先增后减的单峰函数.

这可以感性理解?如果来的次数少,则每次会买贵的,但运费少,若来的次数多,则每次会买便宜的,但运费多.

于是可以三分 $x$ ,考虑在给定 $x$ 时如何计算 $f(x)$ .

每次送外卖时都选择当前最便宜的食物,如果保质期过了,就考虑次便宜的食物,直到买不起了,就退出.

时间复杂度 $O(n\cdot \log S)$ .

注意需要先算一个不算太大的上界.

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e2+10;
int n,cnt=0;
ll f,m;
struct node
{
	ll p,s;
	bool operator < (const node &rhs) const
	{
		return s<rhs.s;
	}
}a[MAXN],b[MAXN];
ll calc(ll x)
{
	ll money=m-x*f;
	if(money<=0)
		return 0;
	ll res=0,tmp=0;
	for(int i=1;i<=cnt;++i)
	{
		ll d=min(b[i].s-tmp,money/(b[i].p*x)); // 买的个数 
		tmp+=d,res+=d*x,money-=d*b[i].p*x;
		if(tmp<b[i].s)
		{
			res+=money/b[i].p;
			break;
		}
	}
	return res;
}
int main()
{
	m=read(),f=read(),n=read();
	for(int i=1;i<=n;++i)
	{
		a[i].p=read();
		a[i].s=read()+1;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
	{
		while(cnt && a[i].p<=b[cnt].p)
			--cnt;
		b[++cnt]=a[i];
	}
	ll L=1,R=m/(f+b[1].p),ans=0;
	while(L<=R)
	{
		ll k=(R-L+1),l=L+k/3,r=L+k*2/3;
		ll vl=calc(l),vr=calc(r);
		if(vl<vr)
		{
			L=l+1;
			ans=vr;
		}
		else
		{
			R=r-1;
			ans=vl;
		}
	}
	cout<<ans<<endl;
	return 0;
}