[bzoj3874/ahoi2014]宅男计划 -凯发k8官方网

description

　　外卖店一共有n种食物，分别有1到n编号。第i种食物有固定的价钱pi和保质期si。第i种食物会在si天后过期。jyy是不会吃过期食物的。比如jyy如果今天点了一份保质期为1天的食物，那么jyy必须在今天或者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这样这份食物就必须在购买当天吃掉。jyy现在有m块钱，每一次叫外卖需要额外付给送外卖小哥外送费f元。送外卖的小哥身强力壮，可以瞬间给jyy带来任意多份食物。jyy想知道，在满足每天都能吃到至少一顿没过期的外卖的情况下，他可以最多宅多少天呢？  

input

　　第一行包含三个整数m，f和n。 　　接下来n行，第i行包含两个整数pi和si。

output

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

 

sample input

32 5 2
5 0
10 2

sample output

3

hint

【样例说明】

jyy的最佳策略是：第一天买一份食物1和一份食物2并且吃一份食物1；第二天吃一份食物2；第三天买一份食物1并且吃掉。  
【数据规模与约定】
对于100%的数据满足0<=si<=10^18,1<=f,pi,m<=10^18,1<=n<=200。 题解：我不能确保这种方法的正确性，因为迄今为止我还没有看到其他能够复杂度能够承受的办法，最起码这样做的话，数据是可以过的，当然不排除数据不够全面。因为送物品非常自由，没有任何限制，所以我们要找一个合适的自变量进行枚举。可以发现，如果我们外卖的次数过少，那么就会出现一些食品性价比不高的情况；如果次数过多，那么就会浪费外卖运费。故可以从这里入手，因为可以看出这是一个类似于二次函数的函数。我们可以通过三分来查找峰值。 　　那么对于每次的求值，就是以贪心为主体了。因为我们显然要价格便宜，保质期又长的食品，故我们将同保质期但价格偏高的去除，然后根据保质期从大到小排序，我们给每一次送餐都加上一个该食品，直到钱不够或者时间已经超过。 代码： --------------------------------------------------------------------------------------------------

#include
#include
#define maxn 205
using namespace std;

typedef long long ll;

struct food { ll p, s; } tmp[maxn], a[maxn];

struct cmp1
{
　　bool operator () (food x, food y)
　　{
　　　　return x.s == y.s ? x.p < y.p : x.s < y.s;
　　}
};
cmp1 cmp1;

struct cmp2
{
　　bool operator () (food x, food y)
　　{
　　　　return x.p < y.p;
　　}
};
cmp2 cmp2;

ll t, m, f, n, tot;

ll getans(ll o)
{
　　ll nowm = m - f * o, d = 0, res = 0, tx;
　　if (nowm < 0) return 0;
　　for (int i = 1; i <= tot; i )
　　{
　　　　ll s = a[i].s, p = a[i].p;
　　　　if (d <= s) tx = min(s - d 1, nowm / (p * o)), res = tx * o, nowm -= p * o * tx, d = tx;
　　　　if (d <= s) tx = min(o, nowm / p), res = tx, nowm -= p * tx, d ;
　　}
　　return res;
}

void init()
{
　　tot = 1;
　　scanf("%i64d %i64d %i64d", &m, &f, &n);
　　for (int i = 1; i <= n; i ) scanf("%i64d %i64d", &tmp[i].p, &tmp[i].s);
　　sort(tmp 1, tmp n 1, cmp1), a[1] = tmp[1];
　　for (int i = 1; i <= n; i ) if (tmp[i].s > a[tot].s) a[ tot] = tmp[i];
　　sort(a 1, a tot 1, cmp2);
}

int main()
{
　　freopen("food.in", "r", stdin);
　　freopen("food.out", "w", stdout);
　　scanf("%i64d", &t);
　　while (t--)
　　{
　　　　init();
　　　　if (f a[1].p > m) { printf("0\n"); continue; }
　　　　ll l = 1, r = m / (f a[1].p), ans = max(getans(l), getans(r));
　　　　while (l <= r)
　　　　{
　　　　　　ll tot = r - l 1, ml = l tot / 3, ansl = getans(ml), mr = l tot * 2 / 3, ansr = getans(mr);
　　　　　　if (ansl < ansr) ans = max(ansl, ans), l = ml 1;
　　　　　　else ans = max(ansr, ans), r = mr - 1;
　　　　}
　　　　for (int i = l; i <= r; i ) ans = max(ans, getans(i));
　　　　printf("%i64d\n",ans);
　　}
　　return 0;
}

--------------------------------------------------------------------------------------------------

转载于:https://www.cnblogs.com/jinkun113/p/4873174.html

总结

以上是凯发k8官方网为你收集整理的[bzoj3874/ahoi2014]宅男计划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。