加油问题
Description
输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含4个正实数，依次为A和B两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、沿途油站数n (1<=n<=200)；第二行含n个实数d1, d2 ,…, dn，表示各油站离出发点的距离（d1=0）；第三行含n个实数p1, p2 ,…, pn，表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。
Input
输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含4个正整数，依次为A和B两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、沿途油站数n (1<=n<=200)；第二行含n个实数d1, d2 ,…, dn，表示各油站离出发点的距离（d1=0）；第三行含n个实数p1, p2 ,…, pn，表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。
Output
对于每个测试例输出一行，含一个实数，表示从城市Ａ到城市Ｂ所要花费的最少油费（输出的结果精确到小数点后一位）。若问题无解，则输出“No Solution”。
Sample Input
2
1500 50 10 4
0 300.0 800.0 1200.0
4.0 5.0 4.0 4.5
1000 40 10 3
0 500.0 750.0
4.5 5.0 4.2
Sample Output
640.0
No Solution
#include <stdio.h>
float d3,c,d2;
float d[100];
int jugement(int n)//判断是否有解,无解是输出"NO SOLUTION"
{
int i;
d3=c*d2;
i=1;
while(i<=n)
{
if((d[i+1]-d[i])>d3)
{printf("No Solution");
printf("\n\n");
return 1;}
i=i+1;
}
return 0;
}
int main()
{
int i,j,k,m,n;
float d1,r,min,ml;
float p[100],x[100];
scanf("%d",&k);
while(k--)
{
scanf("%f %f %f %d ",&d1,&c,&d2,&n);
for(i=1;i<=n;i++)
scanf("%f",&d[i]);
for(i=1;i<=n;i++)
scanf("%f",&p[i]);
d[n+1]=d1;p[n+1]=0;
m=jugement(n);
if(m==1) break;
else
{
min=0;
r=0; //出发时候油箱为空
for(i=1;i<=n;i++)
{
j=i+1;
while(p[j]>=p[i]) //找站i前面油价更便宜的最近一站j
j=j+1;
ml=(d[j]-d[i])/d2;
if(r>=ml)
x[i]=0;
else if(c>=ml)
{x[i]=ml-r;
r=ml;}
else {x[i]=c-r;r=c;}
min=min+x[i]*p[i];
r=r-(d[i+1]-d[i])/d2;
}
printf("%.1f\n",min);
}
printf("\n");
}
return 0;
}
程序可以运行,测试数据也能通过,但为什么上交ACM平台时候不能通过,是不是哪里没想周到还是格式错误
[此贴子已经被作者于2006-5-17 21:52:30编辑过]
