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 <cstdio>
#include <algorithm>
#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

總結

以上是生活随笔為你收集整理的[BZOJ3874/AHOI2014]宅男计划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。