[POJ 1456][Max heap or Disjoint Set] Supermarket

原題連結
唉....最近bug實在是越來越蠢了
本來也是貪心法想了一下就覺得相當好做，結果WA了
改 long long WA了
把priority_queue 放全域，定義完整 WA了
> 改成 < 倒過來做  WA了

最後發現

我寫了
while(scanf("%d",&N)==1 && N)
而測資是可以有N=0的case的＝ ＝
嘖嘖......
-----------------------------------------------------
題解不妨直接看這篇

我是使用max heap的方法，但是並查集更能夠鍛鍊思維，推薦寫看看XD
 

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10000+5;
struct Product
{
    int price,day;
    bool operator < (const Product& rhs) const {return day<rhs.day ;}
}pro[maxn];
int main()
{
    int N;
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++) scanf("%d%d",&pro[i].price,&pro[i].day);
        sort(pro,pro+N);
        priority_queue<int> pq;
        int p=N-1,ans=0;
        for(int day=pro[N-1].day;day;day--)
        {
            while(p>=0 && pro[p].day==day) pq.push(pro[p--].price);
            if(pq.size()) {ans+=pq.top();pq.pop();}
        }
        printf("%d\n",ans);
    }
}