1008 Elevator

The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.

我们城市最高的建筑只有一台电梯。有一个请求列表由 N 个正整数组成，这些数字指定电梯停在哪些楼层，按指定的顺序。电梯每上升一层需要 6 秒钟，每下降一层需要 4 秒钟。电梯每停留一个楼层需要 5 秒钟。

For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.

对于给定的请求列表，你需要计算完成列表中所有请求所需的总时间。电梯在开始时位于 0 层，完成请求后不必返回到底层。

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100.

每个输入文件包含一个测试用例。每个测试用例包含一个正整数 N，后面是 N 个正整数。输入中的所有数字都小于 100。

Output Specification:

For each test case, print the total time on a single line.

对于每个测试用例，输出总时间。

Sample Input:

3 2 3 1

Sample Output:

41

样例说明：

3 2 3 1

3 - 有3个测试样例

2 - 到第2层（0->2）6*(2-0)+5=17

3 - 到第3层（2->3）6*(3-2)+5=11

1 - 到第1层（3->1）4*(3-1)+5=13

我的思路

可以看到，这是一个动态规划问题，输入

N a[1] a[2] a[3] ... a[i] ... a[N]

用curfloor代表现在所在楼层，用res代表总时间，每遍历到一个ai，我们执行：

if(a[i]>curfloor){//如果高于现在所在楼层
    res+=6*(a[i]-curfloor)+5;
    curfloor=a[i];
}else if(a[i]==curfloor){//如果等于现在所在楼层
    res+=5;
}else{//如果低于现在所在楼层
    res+=4*(curfloor-a[i])+5;
    curfloor=a[i];
}

接下来就可以写出整体代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int N;
	cin>>N;
	int a[N];
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	int curfloor=0,res=0;
	for(int i=0;i<N;i++){
		if(a[i]>curfloor){
		    res+=6*(a[i]-curfloor)+5;
		    curfloor=a[i];
		}else if(a[i]==curfloor){
		    res+=5;
		}else{
		    res+=4*(curfloor-a[i])+5;
		    curfloor=a[i];
		}	
	}
	cout<<res;
}

AC

Solution

#include <iostream>
using namespace std;
int main() {
    int a, now = 0, sum = 0;
    cin >> a;
    while(cin >> a) {
        if(a > now)
            sum = sum + 6 * (a - now);
        else
            sum = sum + 4 * (now - a);
        now = a;
        sum += 5;
    }
    cout << sum;
    return 0;
}

可以看到，题解的思路是一个简单的模拟。我的思路是从动态规划的固定思维出发的。

有时候，固定思维会加快解题速度，有时候，固定思维会人为增加复杂度。

练习的时候，还是得拓宽思路，寻找多种解法。最后才能得心应手。