http://acm.pku.edu.cn/JudgeOnline/problem?id=2431
一直通不过,麻烦有兴趣的朋友一起探讨一下

我是这样想的:
1:每次在当前站都往前走到油用完,然后看途经了几个站
2:如果达到终点,那么就输出停下的站数
3:如果没到终点 并且 途经 0 个站,则表示不能到达,输出-1
4:如果没到终点 并且 途径N 个站,那么选取在这几个站中,加了油后能走得最远的
为当前站,然后执行第1步

一直WA,是不是这个算法错了

[此贴子已经被作者于2007-10-15 18:51:51编辑过]

自己顶一下

算法好像是有点问题。

先确认一下，题目中说“The truck now leaks one unit of fuel every unit of distance it travels”，
sample输入中，最近的加油站和卡车距离10，而当前卡车载油也是10，怎么可能到达这个加油站呢？


个人认为这个问题不适合用贪心算法，因为有可能得不到最优解，可以试着用动态规划试试。这是一个组合优化问题。

贪心没错,但不是这样贪的.
下面是我通过的代码:

/**
  &#pku2431.cpp
  @author Eastsun
  @version 1.0 2007/10/14
*/
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

struct Stop{
    Stop(int d,int f){
        dis =d;
        fuel =f;
    }
    int dis;
    int fuel;
};
struct CmpByDis:public binary_function<Stop,Stop,bool>{
    bool operator()(const Stop& s1,const Stop& s2)const{
        return s1.dis >s2.dis;
    }
};
struct CmpByFuel:public binary_function<Stop,Stop,bool>{
    bool operator()(const Stop& s1,const Stop& s2)const{
        return s1.fuel <s2.fuel;
    }
};
int main(){
    int n;
    cin>>n;
    vector<Stop> vec;
    for(int i =0;i <n;i ++){
        int d,f;
        cin>>d>>f;
        vec.push_back(Stop(d,f));
    }
    int dist,fuel,count =0;
    cin>>dist>>fuel;
    sort(vec.begin(),vec.end(),CmpByDis());
    priority_queue<Stop,vector<Stop>,CmpByFuel> queue;
    vector<Stop>::iterator itr =vec.begin();
    for(;;){
        for(;itr!=vec.end()&&fuel>=dist -(*itr).dis;itr ++)
            queue.push(*itr);
        if(queue.empty()){
            cout<<-1<<endl;
            break;
        }
        if(fuel>=dist){
            cout<<count<<endl;
            break;
        }
        fuel += queue.top().fuel;
        queue.pop();
        count ++;
    }
}

这个算法经过鉴定:
神州行,我看行

果然是高手,哦也