luogu4040

题目描述

有个无限量的物品，给定每个的价格和保质期。询问在总价格为，单次配送费为的情况下，最多能吃多少天。

数据范围是，，。

解题思路

较大的数据范围反而提示了本题的做法。我们可以求配送了次最多能吃几天。

考虑这个问题怎么处理。由于每个物品可以选择无限次，因此对于两个物品，费用贵且保质期短肯定更不优秀。换言之，我们维护的序列最终是一个保质期和价格均单调递增的序列。

对于这个序列，我们相当于要选择出元最多能吃多少份的物品。dp的空间复杂度吃不消，我们直接贪心。考虑每个物品最多能吃多少份，可以发现，它必定只有如下两种情况：

1. 剩下的钱全部用来吃本物品。

2. 剩下的钱不能全部用来吃本物品，原因是本物品的保质期限制住了物品数量的增长。

对于情况1，我们分析可以发现，剩下的钱如果连本物品都不能再吃，剩余物品更不可能。因此结束。

对于情况2，我们分析可以发现，本物品一定是吃到保质期了。

因此对于情况1的转移，必定是；

对于情况2的转移，必定是，此处的指的是当前每一次配送的吃的天数。

判断一个物品在不考虑保质期情况下能吃的最大天数为。

如果最大天数小于等于保质期，那就是情况1，反之是情况2.

接下来我们考虑怎么确定这个。我们试想一下，如果h增大，配送次数多，能使用的费用减少，能吃掉的总物品数是一个单峰函数。那么我们可以用三分法来解题。

给出一个三分法的模版：

ll tsearch(ll cost, ll per_cost) {
  ll l = 1, r = cost / per_cost;
  while (l < r) {
    ll lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
    ll lchk = check(lmid, cost - lmid * per_cost);
    ll rchk = check(rmid, cost - rmid * per_cost);
    if (lchk > rchk) r = rmid - 1;
    else l = lmid + 1;
  }
  return max(check(l, cost - l * per_cost), check(r, cost - r * per_cost));
}