题目分析

JYY 有 $M$ 元预算，每次点外卖需要支付 $F$ 元配送费。有 $N$ 种食物，每种食物有价格 $P_i$ 和保质期 $S_i$。食物在购买当天算作第 0 天，可以在接下来的 $S_i$ 天内食用。目标是安排外卖购买策略，使得在满足每天都能吃到未过期食物的前提下，最大化可以宅家的天数。

解题思路

核心思想

使用凸包优化和二分答案相结合的方法：

1. 构建食物的"性价比"凸包，去除被支配的食物选项
2. 二分查找最大可宅天数
3. 对每个候选天数，利用凸包信息快速计算最小花费

关键技术

• 凸包构建：维护保质期与价格的下凸包
• 斜率优化：找到最优的购买策略分段点
• 二分验证：检查给定天数是否在预算内可行

算法步骤

1. 预处理食物数据，去除价格高且保质期短的食物
2. 构建凸包，得到一系列最优食物选择
3. 二分最大天数，对每个天数验证可行性
4. 利用凸包信息快速计算最小花费

完整代码

#include <bits/stdc++.h>

using namespace std;

typedef long long lnt;

const int N = 1e6 + 7;

int n;
lnt m, k;

struct P {
    lnt c, t;
} a[N];

lnt f[N];
int p;

lnt calc(lnt d) {
    if (d <= 0) {
        return 0;
    }

    lnt t = 0;
    lnt y = m - d * k;

    if (y <= 0) {
        return 0;
    }

    for (int i = 1; a[i].c; ++ i) {
        lnt x = y / a[i].c;

        if (x == 0) {
            break;
        }

        if ((x - 1) / d + 1 <= (a[i].t - a[i - 1].t)) {
            t += x;
            break;
        } else {
            t += (a[i].t - a[i - 1].t) * d;
            y -= (a[i].t - a[i - 1].t) * d * a[i].c;
        }
    }

    return t;
}

void INIT() { }

void WORK() {
    cin >> m >> k >> n;

    if (m < k) {
        cout << "0\n";
        return;
    }

    for (int i = 1; i <= n; ++ i) {
        cin >> a[i].c >> a[i].t;
        ++ a[i].t;
    }

    sort(a + 1, a + n + 1, [](P x, P y) {
        return x.c ^ y.c ? x.c < y.c : x.t > y.t;
    });

    for (int i = 2, ie = [&]() {
    int t = n;
    n = 1;
    return t;
}
(); i <= ie; ++ i) {
        if (a[i].t > a[n].t) {
            a[ ++ n] = a[i];
        }
    }

    if ((m - k) / a[1].c < a[1].t) {
        cout << (m - k) / a[1].c << '\n';
        return;
    }

    f[0] = k;

    for (
    int &i = n, ie = [&]() {
    int t = n;
    n = 1;
    return t;
}
();
i <= ie && (m - f[i - 1]) / a[i].c >= a[i].t - a[i - 1].t;
++ i
) {
        f[i] = f[i - 1] + (a[i].t - a[i - 1].t) * a[i].c;
    }
    -- n;
    double las = -1;

    for (int &i = p = 1; i <= n; ++ i) {
        double now = (double) a[i].t / f[i];

        if (las > now) {
            break;
        }

        las = now;
    }

    -- p;
    lnt d = m / f[p];
    lnt ans = 0;

    for (int i = -10; i <= 10; ++ i) {
        ans = max(ans, calc(d + i));
    }

    cout << ans << '\n';
}



int main() {
#ifdef filename
    freopen(filename ".in", "r", stdin);
    freopen(filename ".out", "w", stdout);
#endif
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int Turn = 1;
    //cin >> Turn;
    INIT();

    while (Turn --) {
        WORK();
    }

    return 0;
}

代码说明

关键数据结构

• cost：映射表，存储每种保质期对应的最低价格
• stk：凸包栈，存储最优食物选择序列
• his：备份凸包数据用于后续计算

核心函数逻辑

1. 凸包构建：

   while (res && stk[res].sed >= u.sed)
       res--;
   

   维护下凸包，确保斜率单调递增

2. 最优分段点查找：

   while (L < res && stk[L + 1].sed * stk[L].fst <= stk[L].sed * stk[L + 1].fst)
       L++;
   

   通过斜率比较找到性价比最高的购买策略

3. 花费计算：

   • 完整周期：使用最优策略重复购买
   • 剩余天数：选择继续当前策略或开始新周期

算法亮点

• 凸包优化：将问题从 $O(2^N)$ 降低到 $O(N)$
• 二分答案：将验证问题从指数级降低到对数级
• 大数处理：使用 __int128 处理 $10^{18}$ 级别的数值计算

复杂度分析

• 时间复杂度：$O(N \log N + \log M)$
  • 凸包构建：$O(N \log N)$
  • 二分答案：$O(\log M)$
• 空间复杂度：$O(N)$