题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）

考场上做了半个小时切出来了。

考虑贪心，我们发现只有一中糖果我们会取超过一次。于是我们取

x_i+y_i

最小的。

因为这时我们可以确定其他糖果最多取一次，贪心的按其价值比取就可以了。

最后两个细节：

假如去掉一个取了一次的糖果可以让我们再取两次糖果，此时更优。
假如剩下的够我们再取一个糖果，取了明显更优。

不过民间数据没有第二点，我提供一个。

输入：

CPP

输出：

CPP

代码：

CPP

#include<bits/stdc++.h>
#define int long long
#define double long double
#define set(ai,k) memset(ai,k,sizeof(ai))
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define frep(i,s,t) for(int i=s;i>=t;i--)
#define rep1(i,s,t) for(int i=s;i<t;i++)
#define frep1(i,s,t) for(int i=s;i>t;i--)
#define srt(ai,n) sort(ai+1,ai+n+1)
#define csrt(ai,n,cmp) sort(ai+1,ai+n+1,cmp)
#define pb push_back
#define ppb pop_back
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define pint pair<int,int>
#define fst first
#define scd second
using namespace std;
const int N=1e6+5;
const double eps=1e-8;
int n,m,mn=1e17,ans=0,mx=0;
struct node{
	int a,b;
}vi[N];
bool cmp(node a,node b){
	return a.a<b.a;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie();cout.tie();
	cin>>n>>m;
	rep(i,1,n)cin>>vi[i].a>>vi[i].b,mn=min(mn,vi[i].a+vi[i].b);
	csrt(vi,n,cmp);
	rep(i,1,n)if(vi[i].a<=m&&vi[i].a*2<=mn)ans++,m-=vi[i].a,mx=max(mx,vi[i].a);
	ans+=m/mn*2;
	m%=mn;
	if(mx+m>=mn)m-=mn-mx,ans++;
	rep(i,1,n)if(vi[i].a*2>mn&&vi[i].a<=m)ans++,m-=vi[i].a;
	cout<<ans;
}

题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）

文章操作

相关推荐

评论

题解：P14635 [NOIP2025] 糖果店 / candy（民间数据）