f448 - 1316 - Supermarket
題目描述
題目描述了超商商品銷售的問題，每個商品有其價值和期限。目標是找到一個銷售商品的最佳順序，使得總利潤最大化。每個商品只能銷售一次，且必須在期限內完成銷售。
解題思路
本題採用貪心策略。首先，按照期限降序，價值升序對商品進行排序。然後，使用優先隊列（最大堆）來儲存當前可銷售的商品價值。遍歷排序後的商品列表，按照期限從大到小處理。對於每個期限，將所有期限等於當前期限的商品加入優先隊列。如果優先隊列不為空，則選擇優先隊列中價值最高的商品進行銷售，並將其從優先隊列中移除。重複此過程，直到所有期限都處理完畢。最終，累加所有已銷售商品的價值，即為最大利潤。
複雜度分析
- 時間複雜度: O(N log N)
- 排序商品需要 O(N log N) 時間。
- 遍歷商品列表需要 O(N) 時間。
- 在優先隊列中插入和刪除元素需要 O(log N) 時間，最壞情況下需要 O(N log N) 時間。
- 因此，總時間複雜度為 O(N log N)。
- 空間複雜度: O(N)
- 儲存商品的數組需要 O(N) 空間。
- 優先隊列最多儲存 N 個商品，需要 O(N) 空間。
- 因此，總空間複雜度為 O(N)。
程式碼
#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>
#include <queue>
using namespace std;
struct shop{
int pi,di;
};
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline bool cmp(shop x,shop y){
if(x.di>y.di||(x.di==y.di&&x.pi>y.pi))return 1;
return 0;
}
int main(){
int n;
while(n=read()){
int mt=0,ans=0,it=0;
shop a[n];
for(int i=0;i<n;++i){
a[i].pi=read();
a[i].di=read();
mt=max(mt,a[i].di);
}
sort(a,a+n,cmp);
priority_queue< int > b;
while(mt>0){
while(it<n&&a[it].di==mt){
b.push(a[it].pi);
++it;
}
if(!b.empty()){
ans+=b.top();
b.pop();
}
--mt;
}
write(ans);
putchar_unlocked('\n');
getchar_unlocked();
}
}