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，罚坐四小时。退役！

参考代码

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