题解：P14635 [NOIP2025] 糖果店

省流：新思路。
管理员辛苦了！

题意解释

思路分析

这里介绍一种玄学做法。
由题意知，我们买的第

2n+1

个物品

i

的价钱是

x_i

，买的第

2n

个物品

i

的价钱是

y_i

，那么我们可以看成这个物品

i

的价钱就是

\frac{x_i +y_i}{2}

。
现在我们把要买的商品换一下：一共有

2n

个商品，它们的价钱分别是

x_1

、

\frac{x_1 +y_1}{2}

、

x_2

、

\frac{x_2 +y_2}{2}

到

x_n

、

\frac{x_n +y_n}{2}

。现在把它们排个序，再操作，就行了。
注意！因为浮点数很烦，我就把它们整体乘

2

了（包括

m

）。
详见代码。

代码实现

CPP

#include<bits/stdc++.h> 
#define int long long    
using namespace std;    

const int N=1e5+5;     
struct node{           
	int x;             
	bool op;           
}a[2*N];               //细节2N 
int n,m,cnt,ans;       

bool cmp(node x,node y)
{
	return x.x<y.x;
}

signed main()
{
	cin>>n>>m;          
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;      
		a[++cnt]=node{x*2,0};  // 第一种操作：消耗2x资源，增加1个结果
		a[++cnt]=node{x+y,1};  // 第二种操作：消耗(x+y)资源，可多次执行
	}
	sort(a+1,a+cnt+1,cmp); // 将所有操作按消耗值从小到大排序
	m*=2;                 // 将资源m翻倍，可能是为了处理第一种操作的2x消耗
	
	for(int i=1;i<=cnt;i++)
	{
		if(m<a[i].x) break;   // 如果剩余资源不够当前操作，退出循环
		if(a[i].op==0)        // 第一种操作：消耗固定资源，结果+1
			ans++,m-=a[i].x;
		else                  // 第二种操作：尽可能多次执行，按除法计算
			ans+=m/a[i].x,m%=a[i].x;
	}
	cout<<ans;          
	return 0;
}

战绩可查。

结束！

题解：P14635 [NOIP2025] 糖果店

文章操作

题意解释

思路分析

代码实现

相关推荐

评论

题解：P14635 [NOIP2025] 糖果店