专栏文章

题解:P14167 [Algo Beat Contest 002.5 B] 草莓小蛋糕 (cakes)

P14167题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mino2g0y
此快照首次捕获于
2025/12/02 05:33
3 个月前
此快照最后确认于
2025/12/02 05:33
3 个月前
查看原文

题意

给定一个数nn,表示有几种蛋糕,接着输入nn行,一行三个数,分别表示一种蛋糕的数量CC,原本美味值DD与美味值一天下降数量XX,一天只能吃一块蛋糕,求吃完所有蛋糕后总美味值的最大值(注意:美味值可以降为负数)。

思路

这道题很明显是贪心,一眼不太容易找到思路,可以把题目简化成所有DD的总和在依次减去从00n1n-1乘以一个 XX,我们可以知道,DD的总和是一定的,所以就是要对后半段取最小,这就和接水问题很像了,直接先吃XX最大的即可,这就是本题的贪心思路,不理解的可以看下面代码。

代码

CPP
#include<bits/stdc++.h>
#define int long long//不开long long见祖宗 
using namespace std;
int c[100005],d[100005],x[100005];
signed main(){
	int n,ans=0,sum=0;//ans表示答案 ,sum表示蛋糕数量 
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>d[i]>>x[i];//输入 
		ans+=d[i]*c[i]; //先把原新鲜值统计起来 
		sum+=c[i]; //记录数量  
	}
	int num=0;//天数 
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(x[i]<x[j]){
				swap(x[i],x[j]);
				swap(c[i],c[j]); 
			}
		}
		sum-=(num+num+c[i]-1)*c[i]/2*x[i];//减少美味值 
		num+=c[i]; 
	}//排序 
	cout<<sum; 
	return 0;
} 
为了防抄,特意写了一个伪做法,没有写__int128且排序n2n^2会超时,要改为nlognnlogn做法。

评论

0 条评论,欢迎与作者交流。

正在加载评论...