【題解】ZeroJudge e915: pC. 追求完美的廚師

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e915
【解題想法】Greedy

#include "bits/stdc++.h"
using namespace std;
const int maxn = 100000+5;

struct Customer{
    int f; //火氣指數
    int t; //點的餐所需時間
};

Customer c[maxn];

bool cmp(Customer a, Customer b){
    return b.f * a.t < a.f * b.t;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> c[i].f >> c[i].t;
    }
    sort(c, c+N, cmp);
    
    long long cumTime = 0; //累計完成餐點的時間
    long long ans = 0;
    for (int i = 0; i < N; i++){
        cumTime += c[i].t;
        ans += c[i].f * cumTime;
    }
    cout << ans << "\n";
    return 0;
}
分享本文 Share with friends