P14635 [NOIP2025] 糖果店

· · 题解

已完成今日 0.5h 过 t1 然后坐牢 4h 大学习。

考虑一个结论：假设我们对一个物品选了两次，我们一定不会再对另一个物品选两次，这是显然的。因为可以通过替换来使代价最小。

因此，只会有一件物品被选两次以上，可以发现就是选两次代价最小的那件物品 x。剩下的物品都只会被选一次，且是按代价从小到大选的。

我们枚举有多少个物品只选了一次，计算剩下的代价能选多少次 x 即可。时间复杂度 \mathcal{O(n \log n)}。

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair <ll, ll>

using namespace std;
using ll = long long;

const ll N = 5e5 + 5, M = 320; 

ll n, m;
ll C[N], h = 1e18, s = 0; 

signed main()
{
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);

    FstIO; 

    cin >> n >> m;
    for (ll i = 1; i <= n; ++ i )
    {
        ll x, y; cin >> x >> y; 
        C[i] = x; h = min(h, x + y);
    }
    sort(C + 1, C + n + 1);
    for (ll i = 1; i <= n; ++ i ) C[i] += C[i - 1];
    for (ll i = 0; i <= n; ++ i ) 
    {
        if (m < C[i]) break; 
        s = max(s, i + (m - C[i]) / h * 2);
    }
    cout << s << '\n';

    return 0; 
}

说句闲话：这个 trick 在洛谷进阶算法计划后期的模拟赛里出现过（（（

还不快来报名进阶算法计划！