P14635 [NOIP2025] 糖果店

已完成今日 0.5h 过 t1 然后坐牢 4h 大学习。

考虑一个结论：假设我们对一个物品选了两次，我们一定不会再对另一个物品选两次，这是显然的。因为可以通过替换来使代价最小。

因此，只会有一件物品被选两次以上，可以发现就是选两次代价最小的那件物品

x

。剩下的物品都只会被选一次，且是按代价从小到大选的。

我们枚举有多少个物品只选了一次，计算剩下的代价能选多少次

x

即可。时间复杂度

\mathcal{O(n \log n)}

。

CPP

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair <ll, ll>

using namespace std;
using ll = long long;

const ll N = 5e5 + 5, M = 320; 

ll n, m;
ll C[N], h = 1e18, s = 0; 

signed main()
{
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);
	
	FstIO; 
		
	cin >> n >> m;
	for (ll i = 1; i <= n; ++ i )
	{
		ll x, y; cin >> x >> y; 
		C[i] = x; h = min(h, x + y);
	}
	sort(C + 1, C + n + 1);
	for (ll i = 1; i <= n; ++ i ) C[i] += C[i - 1];
	for (ll i = 0; i <= n; ++ i ) 
	{
		if (m < C[i]) break; 
		s = max(s, i + (m - C[i]) / h * 2);
	}
	cout << s << '\n';
	
	return 0; 
}

说句闲话：这个 trick 在洛谷进阶算法计划后期的模拟赛里出现过（（（

还不快来报名进阶算法计划！

P14635 [NOIP2025] 糖果店

文章操作

相关推荐

评论

P14635 [NOIP2025] 糖果店