应该要判断什么吧

我还是觉得算法不对头，我想个算例来说明一下吧


想好了，看下面这个算例，试着讨论一下：

假设当前卡车有油8，后面一次可达域内的加油站有a,b,c,d，可供油分别为2，4，6，8；按贪心算法，卡车应该忽略加油站a,b,c，直接到达d，此时卡车正好用完油，然而d到其后站e的距离为10，站d可供油仅为8，到不了e，于是算法给出无法到达目的地的结果。

但是事实上卡车只要先到c站，再到d站，就可顺利过去。图如下，请讨论。

[此贴子已经被作者于2007-10-14 21:03:14编辑过]

LS对我的算法理解有误
鉴定完毕

你可以拿我的程序试一下你的数据就知道了.

能具体说下我哪里误解你的算法了吗？你的算法解释很清楚嘛，应该不会误解吧？

"能够到达的加油站"指从起点开始的任何加油站.
考虑d后,还可以再考虑a,b,c的

OK，明白你的意思了，不过这种算法仍然有问题。我的算例中，按你的算法，应该先到站d，发现到不了站e，于是返回站c加油，再往后面的站走。这里问题就出来了，在我的算例中d到e的距离为10，你的算法没问题，但如果改为12的话，你的算法就出问题了。

因为当卡车到d站时油正好用完，在d站加油8，发现到不了e，于是返回c，这时剩油6，在c加油6，一共有油12，而c到e的距离为14，于是给出无法到达的结果。

但如果卡车先到站c，再到站d，然后再往前，是能够到达站e的，这是贪心算法做不到的。

我这个结论有个前提，加油站被加完油后不可重复利用，因为题中给出了加油站能提供油量的上限。


不知道版主是否同意我这个想法？请讨论呵

"发现到不了e，于是返回c"
楼上OOXX，鉴定完毕……

...
你还是没弄清楚我的算法.
我考虑d后再考虑a,b,c并不表示还需要吧车开回去加油!

你还是看代码吧.
或者你能给出一个数据用我的代码得到错误的结果.

我感觉我这样做应该也没有错啊!
思路就是走到第i个站点的时候先看看到第i-1个的时候油还够不够第i个,不够就从前面没取的站点中去油最多的一个
如果够就算了
WA 三次了

#include<stdio.h>
#define inf 6000000
int a[100100][2];
int heap[100100],m;
void shiftup(int l)
{
int i,j,temp;
temp=heap[l];
i=l;
j=i/2;
while(j>=1)
{
if(heap[j]<temp)
{
heap[i]=heap[j];
i=j;
j/=2;
}
else
{
heap[i]=temp;
return ;
}
}
heap[i]=temp;
}
void shiftdown(int l)
{
int i,j,temp;
temp=heap[l];
i=l;
j=i*2;
while(j<m)
{
if(j+1<m&&heap[j+1]>heap[j]) j++;
if(heap[j]>temp)
{
heap[i]=heap[j];
i=j;
j*=2;
}
else
{
heap[i]=temp;
return ;
}
}
heap[i]=temp;
}
int main()
{
int n,i,j,k;
int l,p;
int cnt;
int flag;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
scanf("%d%d",&l,&p);
cnt=0;
j=1;
heap[1]=-1;
m=2;
flag=1;
for(i=n-1;i>=0;i--)
{
while(p<l-a[i][0])
{
if(heap[1]==-1)
{
flag=0;
goto line;
}
p+=heap[1];
heap[1]=-1;
shiftdown(1);
cnt++;
}
heap[m]=a[i][1];
shiftup(m);
m++;
}
line:;
if(flag==0) printf("-1\n");
else printf("%d\n",cnt);
}
}