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

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

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

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

自己顶一下

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

果然是高手,哦也

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

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

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

我也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]