题解：P14635 [NOIP2025] 糖果店

lailai0916 · 2025-11-29 14:05:40 · 题解

题意简述

给定 n 种糖果，每种库存无限。第 i 种糖果的售价循环为 x_i,y_i,x_i,y_i,\dots。求 m 元最多能购买多少颗糖果。

解题思路

考场思路。

我们可以将每种糖果拆分为两类 套装：

• 单颗装：售价 a_i=x_i 元，限购 1 组；
• 两颗装：售价 b_i=x_i+y_i 元，不限组数。

由于两类套装的相互独立，可以将 a 和 b 分别排序。

显然花费随着糖果数量增加 单调递增，我们可以对购买数量 k 进行 二分答案。

计算购买 k 颗糖果的最小花费：将 k 拆分为 k=2p+q，即购买 p 组两颗装和 q 组一颗装。

考虑两类套装的最小花费：

• 单颗装：选择 a_i 最小的前 q 种，即 a_i 的前缀和 s_q；
• 两颗装：选择 p 组 b_i 最小的，即 pb_1。

枚举两颗装组数 p，得到单颗装组数 q=k-2p，此时的总花费为：

关于 p 的范围：由于 k=2p+q，而 0\le q\le n，因此 0\le k-2p\le n，解得：

时间复杂度为 O(n\log m)，注意这个方法要用 __int128。

半小时过 T1，罚坐四小时。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=100005;
ll a[N],b[N];
ll n,m;
bool check(ll k)
{
    __int128 mn=inf;
    for(ll p=max(k-n+1>>1,0ll);p<=k>>1;p++)
    {
        mn=min(mn,__int128(p)*b[1]+a[k-p*2]);
    }
    return mn>m;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        b[i]+=a[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)a[i]+=a[i-1];
    ll l=0,r=inf;
    while(l<r)
    {
        ll mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l-1<<'\n';
    return 0;
}