延迟决策

又名：反悔贪心。

CF1974G

第一天早上你没有钱，每天晚上得到 $X$ 元。在第 $i$ 天里，你可以花费 $C_i$ 元买一个菠萝派。在任何时刻你都不能欠钱，问这 $N$ 天最多能吃多少菠萝派。

先不考虑钱，无脑买。如果钱变成负数，就从之前买过的挑一个最贵的不买，即延迟决策。

i64 sum = 0;
std::priority_queue<int> h;
for (int i = 0; i < N; i++) {
    int c;
    std::cin >> c;
    h.push(c);
    sum -= c;
    if (sum < 0) {
        sum += h.top();
        h.pop();
    }
    sum += X;
}
std::cout << h.size() << "\n";

CF865D

在第 $i$ 天里，菠萝派的价格调整为 $C_i$。你每天要么买一个菠萝派，要么卖一个，要么什么都不干。希望在第 $N$ 天结束时不持有菠萝派，并最大化盈利。

i64 ans = 0;
std::priority_queue<int, std::vector<int>, std::greater<>> h;
for (int i = 0; i < N; i++) {
    int x;
    std::cin >> x;
    if (!q.empty() && q.top() < x) {
        ans += x - q.top();
        q.pop();
        q.push(x);
    }
    q.push(x);
}
std::cout << ans << "\n";