题解：P14635 [NOIP2025] 糖果店

题意简述

给定

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

，此时的总花费为：

pb_1+s_q

关于

p

的范围：由于

k=2p+q

，而

0\le q\le n

，因此

0\le k-2p\le n

，解得：

\max\left(\left\lceil\frac{k-n}{2}\right\rceil,0\right)\le p\le\left\lfloor\frac{k}{2}\right\rfloor

时间复杂度为

O(n\log m)

，注意这个方法要用 __int128。

~~半小时过 T1，罚坐四小时。退役！~~

参考代码

CPP

#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;
}

题解：P14635 [NOIP2025] 糖果店

文章操作

题意简述

解题思路

参考代码

相关推荐

评论

题解：P14635 [NOIP2025] 糖果店