还是我来说吧，嘿嘿我理解了LS的算法了
是这样的：
第一次到d,然后考虑d前面全部的加油站，为什么要考虑呢？这是因为还没到终点。
由于c最多，所以要考虑在c停下加油，于是我们就有在c,d的油了，顺序是先在c加后在d加，然后我们就可以到达比e更远的地方（距离d 14，设为f点）
如果还没有到终点
则考虑
f点以前所有的加油站中油最多的，当然，已经加了的要排除（c, d）， 然后就一直这样循环下去

还是说算法吧，这样看代码很难看的

[此贴子已经被作者于2007-10-14 22:09:20编辑过]

就是走到第i个点的时候先看到第i-1个点的时候油剩下的还够不够到第i个点能就算了.
不能就从前面经过的点中,且没有取的点中取最大的直到能到i点为止要是到不了就是-1了..


其实题目很简单的
可以简化成给你一串数字 a1,a2,a3,a4...
让你从前i个数中取出最少的个数使得和大于某个值就可以了..

我就是想知道这个顺序是怎么通过贪心得到的，如果事先（车到d站前）能知道正确的加油顺序那问题真的解决了。

不把车开回去加油？那车在d站不是哪里也去不了了吗？

还是说算法把，代码看着累，而且同一算法的代码也各有不同的呵。希望能讨论下呵。

我也AC 了
[CODE]/*
*Author: David Hu
*Organization:Harbin Institute of Technology
*Date: From 2007-10-14 21:19:18 to 2007-10-16 18:22:19
*Description: acm.hit.edu.cn Problem 2051
*/
#include <stdio.h>
#include <stdlib.h>
struct node
{
int dis; /* the distance*/
int fuel;
struct node* next;
};
typedef struct node NODE;
typedef struct node* NODE_PTR;
void Create(NODE_PTR*); /* create a link*/
void Get_info_sort(NODE_PTR); /* get all the infomation of the stops and sort as down*/
void Drive (NODE_PTR, NODE_PTR); /* to caculate the result*/
void Insert (NODE_PTR, NODE_PTR); /* insert some link and sort as down*/
int main (void)
{
int s_num; /* the number of stops*/
NODE_PTR head_d, head_f; /* the heads of down sequence distance link and fuel link*/
while(scanf("%d", &s_num) == 1) /* end of run at the end of file*/
{
Create(&head_d);
Create(&head_f);
while(s_num--)
{
Get_info_sort(head_d); /* get all the infomation of the stops and sort as down*/
}
Drive(head_d, head_f);
}
return 0;
}
void Create (NODE_PTR* start_ptr)
{
*start_ptr = (NODE_PTR)malloc(sizeof(NODE) * 1);
(*start_ptr) -> next = NULL;
}
void Get_info_sort (NODE_PTR start_ptr)
{
NODE_PTR new_p, p;
new_p = (NODE_PTR)malloc(sizeof(NODE) * 1);
scanf ("%d%d", &new_p -> dis, &new_p -> fuel);
p = start_ptr;
while(p -> next && p -> next -> dis > new_p -> dis)
{
p = p -> next;
}
new_p -> next = p -> next;
p -> next = new_p;
}
void Drive (NODE_PTR start_ptr_d, NODE_PTR start_ptr_f)
{
int pre_d, pre_f; /* the present distance to the town and the present fuel left*/
int hold, counter = 0;
NODE_PTR p, q;
scanf ("%d%d", &pre_d, &pre_f);
if (start_ptr_d -> next && start_ptr_d -> next -> dis == pre_d)
{
pre_f += start_ptr_d -> next -> fuel;
start_ptr_d = start_ptr_d -> next;
}
hold = pre_d - pre_f;
while(hold > 0)
{
counter++;
p = start_ptr_d;
while(p -> next && p -> next -> dis >= hold)
{
q = (NODE_PTR)malloc(sizeof(NODE) * 1);
q -> dis = p -> next -> dis;
q -> fuel = p -> next -> fuel;
Insert(start_ptr_f, q);
p = p -> next;
free(start_ptr_d);
start_ptr_d = p;
}
if (start_ptr_f -> next == NULL)
{
printf ("-1\n");
return;
}
else
{
hold -= start_ptr_f -> next -> fuel;
start_ptr_f = start_ptr_f -> next;
}
}
printf ("%d\n", counter);
}
void Insert (NODE_PTR start_ptr, NODE_PTR new_p)
{
NODE_PTR p;
p = start_ptr;
while(p -> next && p -> next -> fuel > new_p -> fuel)
{
p = p -> next; /* move to next node*/
}
new_p -> next = p -> next; /* link the new node*/
p -> next = new_p;
}[/CODE]