2014
03-23

# Range

Some automobiles display the estimated driving range, that is, the distance you can expect to drive it (without adding fuel) before running out of fuel. Here is how it works: periodically, the vehicle’s computer records the odometer reading and the weight of fuel in the fuel tank. From this data, the fuel consumption over a certain distance can be computed.
From the fuel consumption and the most recent measurement of fuel tank contents (which we assume is current for all practical purposes), the range can be calculated. Intervals over which the quantity of fuel increased (fuel was added to the tank) will not be used in the computations. For example, in the first problem instance of the sample input, the interval where the fuel weight increased from 29.9 kilograms to 34.2 kilograms will not be used. In this example, 16.3 kilograms of fuel were consumed over a distance of 228.6
kilometers. Therefore, the most recently measured fuel contents of 31.2 kilograms will enable you to drive another 438 kilometers (rounded to the nearest integer). The input will always contain at least one interval (two consecutive lines of input) where no fuel was added to the tank.

The input contains data for a number of problem instances. Each problem instance consists of three or more (odometer reading, fuel weight) pairs, one pair per line. Distances are measured in kilometers and fuel weight in kilograms. All input numbers will be given to one decimal place. The end of each problem instance will be signaled by a (0.0, 0.0) pair. The last problem instance will be followed by a (-1.0, -1.0) pair.

The input contains data for a number of problem instances. Each problem instance consists of three or more (odometer reading, fuel weight) pairs, one pair per line. Distances are measured in kilometers and fuel weight in kilograms. All input numbers will be given to one decimal place. The end of each problem instance will be signaled by a (0.0, 0.0) pair. The last problem instance will be followed by a (-1.0, -1.0) pair.

18400.5 43.2
18440.4 40.4
18482.7 37.0
18540.2 33.1
18585.3 29.9
18620.8 34.2
18664.6 31.2
0.0 0.0
18400.5 43.2
18440.4 40.4
18482.7 37.0
18540.2 33.1
18585.3 29.9
0.0 0.0
-1.0 -1.0

438
415

View Code

#include<stdio.h>
#include<string.h>
const int maxn = 1005;
struct node{
double dis,fuel;
}a[ maxn ];
int main(){
int n=0;
double aa,bb;
while( scanf("%lf%lf",&aa,&bb) && (aa!=-1.0&&bb!=-1.0) ){
a[ n ].dis=aa,a[ n ].fuel=bb,n++;
while( scanf("%lf%lf",&aa,&bb)==2 ){
if( aa==0.0&&bb==0.0 ) break;
a[ n ].dis=aa,a[ n ].fuel=bb,n++;
}
double dis,fuel;
dis=fuel=0;
for( int i=0;i<n-1;i++ ){
if( a[i].fuel>a[i+1].fuel ){
dis+=(a[i+1].dis-a[i].dis);
fuel+=(a[i].fuel-a[i+1].fuel);
}
}
//printf("dis:%lf fuel:%lf\n",dis,fuel);
double ans=a[n-1].fuel*dis/fuel;
//    printf("ans:%.0lf\n",ans);
if(( ans-(double)((int)(ans)) )>0.5) printf("%.0lf\n",( (double)((int)(ans)) )+1.0);
else printf("%.0lf\n",( (double)((int)(ans)) ));
n=0;
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

2. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确