POJ1456貪心（set或者并查集區間合并）

題意：

      給你n商品，每個商品有自己的價值還有保存期限，一天最多隻能賣出去一個商品，問最大收益是多少？

思路：

      比較好想的貪心，思路是這樣，每一次我們肯定拿價值最大的，至于在那天拿當然是盡可能的往後拖了，因為可以把前面的時間留給一些快過期的用，這種貪心政策很容易想到，對于實作的時候我嘗試了兩種方法，首先把商品按照價格從大到小排序，一個是我以前常用的set容器，他可以直接取出一個大于等于x的最小值（隻要加上符号功能就是取最小的最大了），先把所有的天數都當成資源放進set裡，然後對于沒一個物品，如果可以買的話，那麼就消耗離他保存期限最近的那個沒有備用的天，這樣就行了，總的時間複雜度應該是O(n*log(n))的，可以接受，第二個方法我是用的并查集來處理區間合并，思路都是一樣，就是在處理資源（天）的時候用并查集優化時間，比如一開始一個區間 1 2 3 4當第3天用了之後那麼第三天就和第2天合并算一天了 1 2 4，就是這樣每個天數的祖宗存的就是他左側第一個沒有用過的天數。這樣寫的話，如果用上路徑壓縮時間複雜度是O(n)的，比set快不少，如果不用路徑壓縮時間在邏輯上是O(n*n)的，但是剛剛我測試了下，跑了200+ac了。哎！這不重要。呵呵。

并查集+貪心 79ms

#include<stdio.h>

#include<algorithm>

#define N 10000 + 10

using namespace std;

typedef struct

{

    int p ,d;

}NODE;

NODE node[N];

int mer[N];

bool camp(NODE a ,NODE b)

{

    return a.p > b.p;

}

int finds(int x)

{

    return x == mer[x] ? x : mer[x] = finds(mer[x]);

}

int main ()

{

    int n ,ans ,i ,max;

    while(~scanf("%d" ,&n))

    {

        max = 0;

        for(i = 1 ;i <= n ;i ++)

        {

            scanf("%d %d" ,&node[i].p ,&node[i].d);

            if(max < node[i].d) max = node[i].d;

        }

        for(i = 0 ;i <= max ;i ++)

        mer[i] = i;

        ans = 0;

        sort(node + 1 ,node + n + 1 ,camp);

        for(i = 1 ;i <= n ;i ++)

        {

            int x = finds(node[i].d);

            if(!x) continue;

            int y = finds(x-1);

            mer[x] = y;

            ans += node[i].p;

        }

        printf("%d\n" ,ans);

    }

    return 0;

}

set+貪心 474ms

#include<set>

#include<stdio.h>

#include<algorithm>

#define N 10000 + 10

using namespace std;

typedef struct

{

    int p ,d;

}NODE;

NODE node[N];

set<int>myset;

bool camp(NODE a ,NODE b)

{

    return a.p > b.p;

}

int main ()

{

    int n ,i;

    while(~scanf("%d" ,&n))

    {

        int max = 0;

        for(i = 1 ;i <= n ;i ++)

        {

            scanf("%d %d" ,&node[i].p ,&node[i].d);

            if(max < node[i].d) max = node[i].d;

        }

        myset.clear();

        myset.insert(0);

        for(i = 1 ;i <= max ;i ++)

        myset.insert(-i);

        sort(node + 1 ,node + n + 1 ,camp);

        int ans = 0;

        for(i = 1 ;i <= n ;i ++)

        {

            int x = *myset.lower_bound(-node[i].d);

            if(!x) continue;

            ans += node[i].p;

            myset.erase(x);

        }

        printf("%d\n" ,ans);

    }

    return 0;

}