题解：P14635 [NOIP2025] 糖果店

· · 题解

省流：新思路。
管理员辛苦了！

题意解释

题目传送门。

思路分析

这里介绍一种玄学做法。
由题意知，我们买的第 2n+1 个物品 i 的价钱是 x_i，买的第 2n 个物品 i 的价钱是 y_i，那么我们可以看成这个物品 i 的价钱就是 \frac{x_i +y_i}{2} 。
现在我们把要买的商品换一下：一共有 2n 个商品，它们的价钱分别是 x_1、\frac{x_1 +y_1}{2}、x_2、\frac{x_2 +y_2}{2} 到 x_n、\frac{x_n +y_n}{2}。现在把它们排个序，再操作，就行了。
注意！因为浮点数很烦，我就把它们整体乘 2 了（包括 m）。
详见代码。

代码实现

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

const int N=1e5+5;     
struct node{           
    int x;             
    bool op;           
}a[2*N];               //细节2N 
int n,m,cnt,ans;       

bool cmp(node x,node y)
{
    return x.x<y.x;
}

signed main()
{
    cin>>n>>m;          
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;      
        a[++cnt]=node{x*2,0};  // 第一种操作：消耗2x资源，增加1个结果
        a[++cnt]=node{x+y,1};  // 第二种操作：消耗(x+y)资源，可多次执行
    }
    sort(a+1,a+cnt+1,cmp); // 将所有操作按消耗值从小到大排序
    m*=2;                 // 将资源m翻倍，可能是为了处理第一种操作的2x消耗

    for(int i=1;i<=cnt;i++)
    {
        if(m<a[i].x) break;   // 如果剩余资源不够当前操作，退出循环
        if(a[i].op==0)        // 第一种操作：消耗固定资源，结果+1
            ans++,m-=a[i].x;
        else                  // 第二种操作：尽可能多次执行，按除法计算
            ans+=m/a[i].x,m%=a[i].x;
    }
    cout<<ans;          
    return 0;
}

战绩可查。

结束！