旅行家的预算  Problem description 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市 之间的距离D1、汽车油箱的容量C（以升为单位）．每升汽油能行驶的距离D2、出发点每升汽油价格P和沿 途油站数N（N可以为零），油站i离出发点的距Di、每升汽油价格 Pi（ i＝l，2，...N）。计算结果四舍 五入至小数点后两位。如果无法到达目的地，则输出“No solution”。  Input 输入数据的第一行是四个实数；D1 C D2 P分别表示两个城市之间的距离，汽车油箱的容量，每升汽油能行驶的距离，出发点每升汽油价 格；第二行是一个整数N,沿途的油站数。第三行到第N+2，每一行是一个油站的基本信息描述，包括该油站离出发点的距离，该油站每升汽油的价 格。  Output 输出到达目的城市的最小费用(四舍五入到两位小数)，若不能到达目的城市则输出 No solution  Sample Input 275.6  11.9   27.4  2.82102.0  2.9220.0   2.2  Sample Output 26.95 Problem Source NOI // 测试用例275.6  11.9   17.4  2.82102.0  2.9220.0   2.2142.54 275.6  11.9   10.4  2.83 102.0  2.1160.2  2.3220.0  2.262.99 // mycode 2007--6--8 #include <stdio.h>#include <float.h> typedef struct node{ float d; float j; float dist;}NODE; int    main(){  float money,maxoil,totald,speed,price; float tpdist,minj,tdist,maxdist; int   m,i,j,k; NODE  pnode[100];  scanf("%f %f %f %f",&totald,&maxoil,&speed,&price); scanf("%d",&m); for(i = 1; i <= m; i++)  scanf("%f %f",&pnode[i].d,&pnode[i].j); pnode[m+1].j =  pnode[0].d = 0.0; pnode[0].j = price; pnode[m+1].d = totald; maxdist = maxoil * speed; for(i = 0; i <= m; i++){  pnode[i].d = pnode[i+1].d - pnode[i].d;  pnode[i].dist = 0.0;  if(pnode[i].d > maxdist){   printf("No solution\n");   return 0;  } } for(pnode[0].dist=pnode[0].d,i=1; i <= m; i++){  for(j=i-1,tdist = 0.0; tdist < maxdist && j >= 0; j--)   tdist += pnode[j].d;  for(k=j+1,tpdist=pnode[i].d; tpdist > 0.0;){      for(j=k,minj=pnode[j].j; j <= i; j++){    if(minj > pnode[j].j){     k = j;     minj = pnode[j].j;    }   }   if(k == i){    pnode[i].dist += tpdist;    break;   }   for(j=k,tdist=0.0; j < i; j++)    tdist += pnode[j].dist;   if(maxdist-tdist > tpdist)    pnode[k].dist += tpdist;   else    pnode[k].dist += (maxdist-tdist);   tpdist = tpdist + tdist - maxdist;   k++;  } } for(money=0.0,i=0; i <= m; i++)  money = money + pnode[i].dist / speed * pnode[i].j; printf("%.2f\n",money); return 0;}

评论