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.zzzyk.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;
}

作者：ascii991

补充：软件开发 , C++ ,