e915 - pC. 追求完美的廚師
題目描述
題目要求計算將 N 個客人按照特定順序服務，以最小化總火氣值的最佳安排方式。每個客人都有一個火氣指數和點餐所需時間。總火氣值是每個客人火氣指數乘以實際拿到餐點時間的總和。
解題思路
為了最小化總火氣值，我們應該優先服務火氣指數與所需時間的比值較小的客人。這是因為火氣指數較高且所需時間較長的客人，如果延遲服務，會對總火氣值產生更大的影響。因此，我們可以按照火氣指數與所需時間的比值進行排序，然後按照排序後的順序服務客人。具體來說，我們定義一個結構體 yt 包含火氣指數 a 和所需時間 b，然後使用自定義比較函數 cmp 按照 a/b 的大小進行排序。排序後，我們依次計算每個客人的實際拿到餐點的時間（即之前所有客人的點餐時間之和），並將其乘以火氣指數加到總火氣值中。
複雜度分析
- 時間複雜度: O(n log n) 排序操作佔據主導地位，時間複雜度為 O(n log n)。其餘操作，如讀取輸入和計算總火氣值，時間複雜度為 O(n)。
- 空間複雜度: O(n)
需要一個大小為 n 的陣列
a來儲存每個客人的火氣指數和所需時間。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
using namespace std;
struct yt{
long long int a,b;
};
inline long long int read(){
long long int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline bool cmp(yt x,yt y){
if(x.a*y.b>x.b*y.a)
return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
long long int n,ans=0,t=0;n=read();
yt a[n];
for(int i=0;i<n;++i){
a[i].a=read();
a[i].b=read();
}
sort(a,a+n,cmp);
for(int i=0;i<n;++i){
t+=a[i].b;
ans+=a[i].a*t;
}
cout << ans;
}