本文主要是介绍[ACM]Shopping，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
Saya and Kudo go shopping together.
You can assume the street as a straight line, while the shops are some points on the line.
They park their car at the leftmost shop, visit all the shops from left to right, and go back to their car.
Your task is to calculate the length of their route.
You can assume the street as a straight line, while the shops are some points on the line.
They park their car at the leftmost shop, visit all the shops from left to right, and go back to their car.
Your task is to calculate the length of their route.
输入
The input consists of several test cases.
The first line of input in each test case contains one integer N (0<N<100001), represents the number of shops.
The next line contains N integers, describing the situation of the shops. You can assume that the situations of the shops are non-negative integer and smaller than 2^30.
The last case is followed by a line containing one zero.
The first line of input in each test case contains one integer N (0<N<100001), represents the number of shops.
The next line contains N integers, describing the situation of the shops. You can assume that the situations of the shops are non-negative integer and smaller than 2^30.
The last case is followed by a line containing one zero.
输出
For each test case, print the length of their shopping route.
示例输入
4 24 13 89 37 6 7 30 41 14 39 42 0
示例输出
152 70
提示
Explanation for the first sample: They park their car at shop 13; go to shop 24, 37 and 89 and finally return to shop 13. The total length is (24-13) + (37-24) + (89-37) + (89-13) = 152
解题思路：一开始没有多想算法，第一反应就是先排序，再把排序（从小到大)后的几个距离数值放在数组a[]中，然后用一个循环 sum+=（ a[j+1]-a[j] ），最后再加上 最大距离 - 最小距离 ，输出最终sum，结果提交超时。后来又想了想算法，发现 原来sum+=（ a[j+1]-a[j] ）的结果和 最大距离与最小距离的差相等，因此本题不需要排序，只要找出数组中最小的数min，和最大的数max 即可， 用公式 sum=2*(max-min)，输出sum就可以了，问题通过。本题再次证明了算法的重要性。 Ps：本题里的提示部分是个陷阱啊！
代码：
#include <iostream>
using namespace std;
int main()
{int N,i;while(cin>>N&&N!=0){int a[100001],min,max;for(i=1;i<=N;i++)cin>>a[i];min=a[1];max=a[1];for(i=2;i<=N;i++){if(a[i]>max)max=a[i];if(a[i]<min)min=a[i];}int sum=0;sum=2*(max-min);//最重要的一步cout<<sum<<endl;}return 0;
}
这篇关于[ACM]Shopping的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
