专栏文章

P14635 [NOIP2025] 糖果店 / candy 题解

kkxkk665
P14635题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimy28xe
此快照首次捕获于
2025/12/01 17:25
3 个月前
此快照最后确认于
2025/12/01 17:25
3 个月前
查看原文

前言

考场的想法，结果2.5h都还有一些细节没处理好导致有点小爆炸。

思路

首先阅读题目和样例，根据样例1可以发现：对于大量购买同一种糖果的情况，平均每颗的价格为 xi+yi2\frac{x_i + y_i}{2}。因此 xi+yix_i + y_i 最小的糖果在批量购买时最优，可以想到去找到这颗糖果 pp 并大量购买。
再看到样例2，发现我们不能只买 pp 这一个糖果，因为可能有其他的糖果在第一次购买时的价格比 pp 的更便宜，买了后的糖果数比只买 pp 的更多。这些糖果 ii 的第一颗价格 xix_i 很低，但第二颗价格 yiy_i 很高，平均价格不优，只适合买一颗。
可以发现对于 pp 以外的糖果，买 xx 较小的糖果肯定比买 xx 较大的糖果优，因此我们就可以对价格按 xx 从小到大排序，之后枚举买前 kk 颗其他糖果的情况并统计其买的钱数 sumsum，然后用 mm 减去 sumsum 得到剩余的钱数去计算买 pp 的个数，取每种情况的最大值即可。
有人可能会问：假如说单买的糖果里有可以买第二颗的情况怎么办？但这其实不会成立，如果单买的糖果 ii 可以买第二颗，则需要花费 xi+yix_i + y_i，但此时 xi+yi≥xp+ypx_i + y_i \ge x_p + y_p，同样的钱用来买 pp 糖果必定可以得到 22 颗，甚至还有可能可以再买一颗 pp，而买 ii 只能得到 22 颗，总糖果数没有更优，因此不会选择买 ii 的第二颗。

时间复杂度

主要集中在 sort 的排序上，为 O(nlogn)O(nlogn)，枚举是 O(n)O(n) 的，计算钱数和颗数都是 O(1)O(1) 的，因此总复杂度是 O(nlogn)O(nlogn)。

代码

一些解释和注意事项都写在注释里了。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,mn=1e18,p;
struct node
{
	ll x,y;
}cd[100005];
bool cmp(node a,node b)
{
	if(a.x==b.x) return a.y<b.y;
	else return a.x<b.x;
}
ll check(ll sum,ll nk)//算买p的颗数并加到当前情况的答案中，注意这里的数据类型是long long
{
	ll w=m-sum;//剩余的钱数，注意这里的数据类型也是long long
	nk+=(w/mn)*2;
	if(w-(w/mn)*mn>=cd[p].x) nk++;//求买p的颗数，注意这里等于的时候也是可以买一颗p的
	return nk;
} 
int main() 
{
    ios::sync_with_stdio(false);
  	cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
    	cin >> cd[i].x >> cd[i].y;
    	mn=min(mn,cd[i].x+cd[i].y);//mn是x+y最小值
	}
	sort(cd+1,cd+n+1,cmp);
	for(int i=1;i<=n;i++) if(cd[i].x+cd[i].y==mn) p=i;//p是x+y最小的位置 
	ll sum=0,ans=check(0,0),mk=0;//mk是当前买的散的糖果数，注意ans一开始要为只买p糖果时的答案
	for(int i=1;i<=n;i++)
	{
		if(i==p) continue;//糖果p在后面check函数中会单独统计，因此在这里不考虑
		sum+=cd[i].x;
		if(sum>m) break;//超过m就说明这颗和之后的糖果都买不下了
		mk++;
		ans=max(ans,check(sum,mk));
	}
	cout << ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...