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>函数。
#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(){ 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;}