题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）

· · 题解

糖果购买问题 题解

题目背景

小 R 有 m 元钱，要在 n 种糖果中购买尽可能多的糖果。每种糖果的购买价格是周期变化的。

题目分析

对于第 i 种糖果：

解题思路

省流：贪心。

关键观察

  1. 每两颗糖果的花费固定：任意连续两颗糖果总花费为 x_i + y_i 元
  2. 贪心策略：优先选择平均价格低的糖果批量购买

算法步骤

  1. 计算所有糖果的 sum_i = x_i + y_i
  2. 按 sum_i 从小到大排序
  3. 尽量购买"两颗一组"的组合
  4. 用剩余的钱优化购买：
    • 买一颗新糖果（选最小 x_i）
    • 替换策略：用更便宜的单颗换掉贵的组合

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    int n;
    ll m;
    cin >> n >> m;

    vector<ll> x(n), y(n), sum(n);
    ll min_x = 1e18, min_y = 1e18;

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i]；
        sum[i] = x[i] + y[i]；
        min_x = min(min_x, x[i])；
        min_y = min(min_y, y[i])；
    }

    sort(sum.begin(), sum.end())；

    ll ans = 0;
    ll cost = 0;

    // 批量购买两颗一组的组合
    for (int i = 0; i < n; i++) {
        if (cost + sum[i] <= m) {
            cost += sum[i];
            ans += 2；
        } else {
            break；
        }
    }

    ll remaining = m - cost;

    // 情况1：买一颗新的糖果
    if (remaining >= min_x) {
        ans = max(ans，ans + 1);
    }

    // 情况2：替换策略
    if (ans >= 2) {
        ll new_remaining = remaining + sum[ans/2 - 1] - min_y;
        if (new_remaining >= min_x) {
            ans = max(ans, ans - 2 + 3);
        }
    }

    // 情况3：钱太少
    if (min_x > m && min_y > m) {
        ans = 0;
    }

    cout << ans << endl;

    return 0;
}

警告：代码中含有防抄袭改动，请勿直接复制！！