返回题解分享
讨论 / 题解分享/ 帖子详情

训练士兵(编程题) - 题解

贪心+前缀和

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

using ll=long long;
const int N=1e5+9;
ll n,s,pre[N],ans,tuanti;
struct node
{
	ll p,c;
	bool operator<(const node &i)const
	{
		return c<i.c;
	}
}a[N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>s;
	for(int i=1;i<=n;i++)cin>>a[i].p>>a[i].c;
	sort(a+1,a+1+n);
	for(int i=n;i>=1;i--)pre[i]=pre[i+1]+a[i].p;
	//for(int i=1;i<=n;i++)cout<<pre[i]<<' ';cout<<'\n';
	
	for(int i=1;i<=n;i++)
	{
		if(tuanti==a[i].c)continue;
		if(s<=pre[i])
		{
			ans+=(a[i].c-tuanti)*s;
			tuanti=a[i].c;
		}else if(s>pre[i])
		{
			ans+=(a[i].c-tuanti)*a[i].p;
			//tuanti=a[i].c;
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*Ac
*/
1 回复 0 转发 0 喜欢 2 阅读
回复 (1)
默认 最新
露米 2026/2/12
谢谢你的分享。思路很清晰呢,通过排序和前缀和来优化贪心的判断过程,确实是一个很高效的做法。

代码结构也很整洁,尤其是处理“团体训练”和“个人训练”成本切换的逻辑,写得挺直观的。对于正在学习贪心算法的朋友来说,这份题解很有参考价值。

在写这道题的时候,你是第一时间就想到了用前缀和来辅助判断,还是在调试过程中慢慢优化的呢 🙂
期待看到你后续更多的思路分享。如果其他小伙伴在阅读代码时有不明白的地方,或者有不一样的解法,也欢迎在评论区一起交流。

大家共同进步的过程,也是一种很有趣的学习方式。
0