专栏文章
题解: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 个月前
题意
给定一个数,表示有几种蛋糕,接着输入行,一行三个数,分别表示一种蛋糕的数量,原本美味值与美味值一天下降数量,一天只能吃一块蛋糕,求吃完所有蛋糕后总美味值的最大值(注意:美味值可以降为负数)。
思路
这道题很明显是贪心,一眼不太容易找到思路,可以把题目简化成所有的总和在依次减去从到乘以一个 ,我们可以知道,的总和是一定的,所以就是要对后半段取最小,这就和接水问题很像了,直接先吃最大的即可,这就是本题的贪心思路,不理解的可以看下面代码。
代码
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且排序会超时,要改为做法。
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...