CodeForces - 144A Arrival of the General （简单搜索）

81 阅读 0 评论 54 点赞

我是靠谱客的博主炙热犀牛，最近开发中收集的这篇文章主要介绍CodeForces - 144A Arrival of the General （简单搜索），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A Ministry for Defense sent a general to inspect the Super Secret Military Squad under the command of the Colonel SuperDuper. Having learned the news, the colonel ordered to all n squad soldiers to line up on the parade ground.
By the military charter the soldiers should stand in the order of non-increasing of their height. But as there’s virtually no time to do that, the soldiers lined up in the arbitrary order. However, the general is rather short-sighted and he thinks that the soldiers lined up correctly if the first soldier in the line has the maximum height and the last soldier has the minimum height. Please note that the way other solders are positioned does not matter, including the case when there are several soldiers whose height is maximum or minimum. Only the heights of the first and the last soldier are important.
For example, the general considers the sequence of heights (4, 3, 4, 2, 1, 1) correct and the sequence (4, 3, 1, 2, 2) wrong.
Within one second the colonel can swap any two neighboring soldiers. Help him count the minimum time needed to form a line-up which the general will consider correct.
Input
The first input line contains the only integer n (2 ≤ n ≤ 100) which represents the number of soldiers in the line. The second line contains integers a1, a2, …, an (1 ≤ ai ≤ 100) the values of the soldiers’ heights in the order of soldiers’ heights’ increasing in the order from the beginning of the line to its end. The numbers are space-separated. Numbers a1, a2, …, an are not necessarily different.
Output
Print the only integer — the minimum number of seconds the colonel will need to form a line-up the general will like.
Examples
Input
4
33 44 11 22
Output
2
Input
7
10 10 58 31 63 40 76
Output
10
Note
In the first sample the colonel will need to swap the first and second soldier and then the third and fourth soldier. That will take 2 seconds. The resulting position of the soldiers is (44, 33, 22, 11).
In the second sample the colonel may swap the soldiers in the following sequence:
1.(10, 10, 58, 31, 63, 40, 76)
2.(10, 58, 10, 31, 63, 40, 76)
3.(10, 58, 10, 31, 63, 76, 40)
4.(10, 58, 10, 31, 76, 63, 40)
5.(10, 58, 31, 10, 76, 63, 40)
6.(10, 58, 31, 76, 10, 63, 40)
7.(10, 58, 31, 76, 63, 10, 40)
8.(10, 58, 76, 31, 63, 10, 40)
9.(10, 76, 58, 31, 63, 10, 40)
10.(76, 10, 58, 31, 63, 10, 40)
11.(76, 10, 58, 31, 63, 40, 10)
问题链接：http://codeforces.com/problemset/problem/144/A
问题简述：输入数n代表有n名士兵，下面一行输入每位士兵的身高，每次使一名士兵向左或向右移动一步，要求输出使最前面为最高的士兵，最后面为最矮的士兵的最短步数
问题分析：从左向右找出最高的士兵在第几位，从右向左找出最矮的士兵在第几位，输出和-1即可，注意如果最高士兵位数>最矮士兵位数则要再-1（两位可交换省一步）
AC通过的C++语言程序如下：

#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int *p = new int[n];
for (int i = 0; i < n; i++)
{
cin >> p[i];
}
int min = 0, max = 0;
for (int i = 0; i < n; i++)
{
int findma2 = 0;
for (int j = i + 1; j < n; j++)
{
if (p[i] < p[j]) { break; }
findma2++;
}
if (findma2 == n - 1 - i) {
max = i; break; }
}
for (int i = n-1; i >= 0; i--)
{
int findmi2 = 0;
for (int j = i - 1; j >= 0; j--)
{
if (p[i] > p[j]) { break; }
findmi2++;
}
if (findmi2 == i) { min = i; break; }
}
int res = max + n - 1 - min;
if (max > min) { res--; }
cout << res;
return 0;
}