http://acm.pku.edu.cn/JudgeOnline/problem?id=2431
一直通不过,麻烦有兴趣的朋友一起探讨一下
我是这样想的:
1:每次在当前站都往前走到油用完,然后看途经了几个站
2:如果达到终点,那么就输出停下的站数
3:如果没到终点 并且 途经 0 个站,则表示不能到达,输出-1
4:如果没到终点 并且 途径N 个站,那么选取在这几个站中,加了油后能走得最远的
为当前站,然后执行第1步
一直WA,是不是这个算法错了
[此贴子已经被作者于2007-10-15 18:51:51编辑过]
----------------解决方案--------------------------------------------------------
自己顶一下
----------------解决方案--------------------------------------------------------
当公务员后N久没搞ACM了,不过帮着看下呵,如果有思路和你讨论一下呵
----------------解决方案--------------------------------------------------------
算法好像是有点问题。
先确认一下,题目中说“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 ++;
}
}
----------------解决方案--------------------------------------------------------
楼上的能说下算法思想吗?怎么个贪法?
----------------解决方案--------------------------------------------------------
就是在能够到达的加油站里面选择一个油量最大的加油.
然后再在能够到达的加油站里面选择一个油量最大的加油.
...
直到能够到达终点,或者到达不了任何加油站.
----------------解决方案--------------------------------------------------------
这个算法我开始就考虑过,应该是行不通的。你的程序确实通过了?
----------------解决方案--------------------------------------------------------
这个算法经过鉴定:
神州行,我看行
果然是高手,哦也
----------------解决方案--------------------------------------------------------
你们说的是C吗?我怎么看不懂。我是菜鸟!
----------------解决方案--------------------------------------------------------