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

· · 题解

题意

给定一个数n,表示有几种蛋糕，接着输入n行，一行三个数，分别表示一种蛋糕的数量C,原本美味值D与美味值一天下降数量X，一天只能吃一块蛋糕，求吃完所有蛋糕后总美味值的最大值（注意：美味值可以降为负数）。

思路

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

代码

#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且排序n^2会超时，要改为nlogn做法。