poj 貪心小結（一）

本次貪心題的練習題有:2325,3258,3122,2393,1065,1323,1328,1700

1700:經典的過河問題。兩種貪心策略，一種是最快的+最慢的，最快的回來，再最快的+次慢的，最快的回來，第二種是最快的+次快的，次快的回來，再最慢+次慢過河，在最快的回來。兩中策略的結果都是最慢的和次慢的過了河。然後就可以dp，注意n=1,2,3特判。

2325：貪心+高精度

3258：二分

3122：二分

2393：對於第i周的生產，兩種情況,一是用本周的單價c[i]，二是采用前面某周的單價c[j]+（i-j)*s。可以用二叉堆優化。

1065：排序,求最長不下降子序列。（dilworth定理）

1323：水，很簡單的貪心策略，但要考慮周全，特別是不要忘了n個人都出牌，不能夠只考慮自己和其中一個對手。

1328：對每個島嶼以d為圓心畫圓，與x軸求交點，得到了若干線段，然後就是熟悉的貪心問題了。但要注意，被包含的線段一定不能忽略。

給出2393的代碼，因為二叉堆的維護比較有技巧性。而且使用了priorty_queue和greater<int>函數。

[cpp] 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <algorithm> 
#include <queue> 
using namespace std; 
 
const int N=10005; 
 
priority_queue<int,vector<int>,greater<int> > h; 
long long ans; 
int c[N],y[N]; 
int n,s,tmp; 
 
int main() www.2cto.com
{ 
    int i; 
    freopen("in.txt","r",stdin); 
 
    scanf("%d%d",&n,&s); 
    for (i=1;i<=n;i++) 
        scanf("%d%d",&c[i],&y[i]); 
    ans=0; 
    for (i=1;i<=n;i++) 
    { 
        tmp=c[i]; 
        if (h.size()>0) tmp=min(tmp,h.top()+i*s); 
        ans+=(long long)tmp*y[i]; 
        h.push(c[i]-i*s); 
    } 
    cout << ans << endl; 
}