[洛谷P4040] AHOI2014 宅男计划

题目背景

自从迷上了拼图，JYY就变成了个彻底的宅男。为了解决温饱问题，JYY不得不依靠叫外卖来维持生计。

问题描述

外卖店一共有N种食物，分别有1到N编号。第i种食物有固定的价钱Pi和保质期Si。第i种食物会在Si天后过期。JYY是不会吃过期食物的。

比如JYY如果今天点了一份保质期为1天的食物，那么JYY必须在今天或者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这样这份食物就必须在购买当天吃掉。

JYY现在有M块钱，每一次叫外卖需要额外付给送外卖小哥外送费F元。

送外卖的小哥身强力壮，可以瞬间给JYY带来任意多份食物。JYY想知道，在满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？

输入格式

第一行包含三个整数M，F和N。

接下来N行，第i行包含两个整数Pi和Si。

输出格式

输出仅包含一行一个整数表示JYY可以宅的最多的天数。

样例输入

32 5 2

5 0

10 2

样例输出

说明

【样例说明】

JYY的最佳策略是：

第一天买一份食物1和一份食物2并且吃一份食物1；

第二天吃一份食物2；

第三天买一份食物1并且吃掉。

【数据规模与约定】

对于100%的数据满足0<=Si<=10^{18,1<=F,Pi,M<=10}18,1<=N<=200

解析

首先比较重要的是看出送外卖的次数和能够活的天数是一个单峰函数的关系。那么我们可以采用三分法求最大值。

现在的问题是如何已知送外卖的次数求能够活的最多的天数。考虑对每一次送外卖进行贪心，肯定是从最便宜的买起，能吃几天就吃几天，吃不了了就买次便宜的。这样我们最后肯定还剩了钱，即每次的余数。对于剩余的这部分我们用同样的方法来贪心，但不能作为单独的一次外卖。所以，我们从之前贪心时买到的外卖开始而不是从最便宜的开始。

代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#define int long long

#define N 202

using namespace std;

struct food{

	int p,s;

}a[N];

int n,m,f,i;

int read()

{

	char c=getchar();

	int w=0;

	while(c<'0'||c>'9') c=getchar();

	while(c<='9'&&c>='0'){

		w=w*10+c-'0';

		c=getchar();

	}

	return w;

}

int my_comp(const food &x,const food &y)

{

	if(x.p==y.p) return x.s>y.s;

	return x.p<y.p;

}

int cal(int x)

{

	int sum=m-x*f,ave=sum/x,rem=sum-ave*x,ans1=0,ans2=0,j=1;

	for(int i=1;i<=n;i++){

		if(a[i].s>=ans1&&ave>=a[i].p){

			int tmp=min(a[i].s-ans1+1,ave/a[i].p);

			ans1+=tmp;

			ave-=tmp*a[i].p;

		}

		if(ave<a[i].p){

			j=i;

			break;

		}

	}

	rem+=ave*x;

	for(int i=j;i<=n;i++){

		if(a[i].s>=ans1&&rem>=a[i].p){

			ans2=min(rem/a[i].p,x);

			break;

		}

	}

	return ans1*x+ans2;

}

signed main()

{

	m=read();f=read();n=read();

	for(i=1;i<=n;i++) a[i].p=read(),a[i].s=read();

	sort(a+1,a+n+1,my_comp);

	int l=1,r,midl,midr;

	if(f!=0) r=(m/f)+1;

	else r=m+1;

	while(l<r){

		midl=l+(r-l)/3;

		midr=r-(r-l)/3;

		if(cal(midl)>=cal(midr)) r=midr-1;

		else l=midl+1;

	}

	printf("%lld\n",cal(l));

	return 0;

}

巴特西