贪心

貪心算法：指再對問題求解的時候，總是做出在當前看來是最好的選擇，也就是不從整體上考慮最優，做出的是局部的最優解；

看一下這題就明白了：

這題題意要注意，ddl是同一天的商品也可以都獲利，比如他們的ddl都是2，那麼就可以在第0天和第1天都賣了，一開始理解錯了，

看了Discuss裡面給的測試數據才發現這個問題...

是貪心地選取最大獲利的商品，然後用一個vis[]數組標記他在那一天出售，其他就不可以在這一天出售了:

 1 // poj 1456.Supermarket
 2 // 贪心 + 并查集 
 3 // references:
 4 // http://www.cnblogs.com/lzmfywz/p/3208746.html
 5 // http://www.cnblogs.com/rainydays/archive/2011/06/20/2085269.html
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 
11 using namespace std;
12 
13 const int N = 100005;
14 
15 struct Product {
16     int val;
17     int ddl;
18 }p[N];
19 
20 int vis[N];
21 
22 bool cmp(Product a, Product b)
23 {
24     return a.val > b.val;
25 }
26 
27 int main()
28 {
29     int n;
30     while(scanf("%d", &n) != EOF)
31     {
32         memset(vis, 0, sizeof(vis));
33         int maxn = -1;
34         for(int i=0; i<n; i++)
35         {
36             scanf("%d%d", &p[i].val, &p[i].ddl);
37         }
38         sort(p, p + n, cmp);
39         int ans = 0;
40         for(int i=0; i<n; i++)
41         {
42             for(int j=p[i].ddl; j>=1; j--)    //从大到小，不然大的val占了小的 
43             {
44                 if(!vis[j])
45                 {
46                     vis[j] = 1;
47                     ans += p[i].val;
48                     break;
49                 }
50             }
51         }
52         printf("%d
", ans);
53         
54     }
55     return 0;
56 }

還有就是看Discuss裡面說道的時間問題，說是現場賽的測試數據很大，所以必須要用幷查几優化，也就是查找的時候不能用線性，回超時，至於怎麼優化，

我遲點再看看吧..對幷查集真是心累...