#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
struct Lo{
    int oil,lo;
    bool friend operator < (Lo a,Lo b)
    {
         return a.lo>b.lo;
    }
}s[10001];
int main()
{
  //  freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    int n,l,p,i,j,k,cover,len,ans; //最后三个分别是 最大到达距离，堆长度，计算结果 
    int sta[10001];  // 油站的堆数组 
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++) scanf("%d%d",&s[i].lo,&s[i].oil);
        sort(s,s+n);  // 按路程从大到小排序 
        scanf("%d%d",&l,&p);
        cover=l-p;  //不用加油能走到位置 
        len=ans=0;
        for(i=0;i<n;i++) if(s[i].lo<=l) break;   //把在原始位置后面的省略  
        while(cover>0){  // 只要能继续前行 
            for(;i<n;i++){
                if(s[i].lo<=cover){ // 在能走到的范围内，都把油加进堆中 
                    sta[len++]=s[i].oil;  // 压堆 
                    push_heap(sta,sta+len); 
                }
            }
            if(len==0) break; //如果堆中没有元素，而cover的路程又没有到终点，则失败 
            cover -= sta[0];  // 减去最大的油 
            ans++;           //计数器加1 
            pop_heap(sta,sta+len); // 出堆 
            len--;
        }
        if(cover>0) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 1;
}

• Re:第一次贴wa的代码让高手们给我查错,真不好意思,我也用stl的heap+greedy (128) yuanyirui 2007-04-03 09:28:16
• Re:第一次贴wa的代码让高手们给我查错,真不好意思,我也用stl的heap+greedy (20) zhhy_oi 2008-02-23 14:43:53
  • Re:第一次贴wa的代码让高手们给我查错,真不好意思,我也用stl的heap+greedy (26) Liuzhaoliang 2008-09-11 16:17:40
    • 可能现在回复有点晚，但是是我看过了你的代码后，查查了push_heap（）这个算法函数，用你的代码真的AC了，原题只有一个case,而你循环读入。。。。你就错在了这里。可能是其他OJ一般都是多个case吧，POJ经常只有一个case. (117) Liuzhaoliang 2008-09-11 16:19:55