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

zhengpie · 2025-11-29 14:50:23 · 题解

0.前言

不能参加今年的 NOIP，大概是今年最大的遗憾吧。

1.思路

首先看到 n \leq 10^5，结合题面，很容易想到 O(n \log n) 的做法，那就是贪心。其中复杂度的瓶颈在于排序。

我们考虑将糖果两颗两颗的拿，那么显然可以找到一个 d，使得 d \leq (x_i+y_i),i \in [1,n]。显然，我们会一直买两次价格之和为 d 的这种糖果。

但是，我们会发现问题：如果 \exist 1 \leq i < j \leq n,x_i+x+j <d 这种时候我们买糖果 i 和糖果 j 各一颗显然更划算。于是我们要先处理这种情况，然后再一直买两次价格之和为 d 的糖果。

然而，最后可能还剩 k 块钱，且 k < d。此时只要遍历一遍所有的糖果判断一下就可以了。

2.代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ioimprove(); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FILE(x); freopen(x".in","r",stdin);freopen(x".out","w",stdout);
int n,m,cnt,minn = 2147483647;
struct node
{
    int val1,val2;
}a[214514];
bool cmp2(node x,node y)
{
    return x.val1 < y.val1;
}
signed main()
{
    ioimprove();
    //FILE("candy");
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
        cin>>a[i].val1>>a[i].val2,minn = min(minn,a[i].val1 + a[i].val2);
    sort(a + 1,a + n + 1,cmp2);
    for(int i = 1;i <= n;i++)   
    {
        if(i < n && m >= (a[i].val1 + a[i + 1].val1) && ((a[i].val1 + a[i + 1].val1) <= minn))
        {
            m -= (a[i].val1 + a[i + 1].val1);
            cnt += 2;
            i++;
            continue;
        }
        else if(m % minn >= a[i].val1)
        {
            m -= a[i].val1;
            cnt++;
        }
    }
    cnt += (m / minn) * 2;
    m %= minn;
    cout<<cnt;

    return 0;
}