547
九度1398：移動次數
題目1398：移動次數
時間限製：1 秒
內存限製：32 兆
特殊判題：否
提交：1331
解決：346
題目描述：
眾所周知JOBDU旗下的JOBBALA公司是一家以個性、親民著稱的IT公司。在JOBBALA公司成立50周年的日子裏，公司CEO組織全體員工登山旅遊。按照往常的習慣，導遊通常要求遊客按照身高從低到高的順序排好，但是考慮這次JOBBALA人數太多，排序很耗時間。因此，導遊想了想，要求JOBBALA的員工可以隨便排，但是必須保證隊列的第一個是隊列中最矮的，隊列的最後一個是隊列中最高的。例如：隊列 { 1, 4, 3, 2, 2, 5} 就是符合的隊列，{1, 4, 2, 3, 2, 5}也符合，而{2, 1, 2,
3, 4, 5}就是錯的。請問對於任意的隊列，最少要兩兩交換多少次，可以讓其符合導遊的要求？
輸入：
輸入有多組測試案例，每個測試案例為2行。
第一行包括一個整數n（2<=n<=200）表示人數，接下來一行包括n個整數a1, a2, …… an (1<=ai<=200) 表示n個員工初始的排列。
輸出：
對應每個測試案例，按照導遊的要求，輸出最少需要兩兩交換的次數。
樣例輸入：
2
89 88
4
55 88 1 2
樣例輸出：
1
3
提示：
案例2中，最少需要移動三次：(55 88 1 2) -> (55 1 88 2) -> (1 55 88 2) -> (1 55 2 88)
思路：題不難，隻是處理重複的最大值和最小值有點小技巧
AC代碼：
#include<stdio.h>
#include<string.h>
#include<limits.h>
int a[300];
int main()
{
int i,j,n,max,min,maxnum,minnum,t,sum;
while(scanf("%d",&n)!=EOF)
{
maxnum=INT_MIN;minnum=INT_MAX;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
if(a[i]>=maxnum)
{max=i;maxnum=a[i];}
if(a[i]<minnum)
{min=i;minnum=a[i];}
}
sum=0;
if(n-1-max<=min)
{
for(i=max;i<n-1;i++)
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
sum++;
}
for(i=0;i<n;i++)
{
if(a[i]==minnum)
{min=i;minnum=a[i];break;}//注意，這裏加break的原因就是如果有兩個以上相同的最小值，則選擇最靠左的
}
for(i=min;i>0;i--)
{
t=a[i];
a[i]=a[i-1];
a[i-1]=t;
sum++;
}
printf("%d\n",sum);
}
else
{
for(i=min;i>0;i--)
{
t=a[i];
a[i]=a[i-1];
a[i-1]=t;
sum++;
}
for(i=0;i<n;i++)
{
if(a[i]==maxnum)
{max=i;maxnum=a[i];}//注意，這裏不加break的原因就是如果有兩個以上相同的最大值，則選擇最靠右的
}
for(i=max;i<n-1;i++)
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
sum++;
}
printf("%d\n",sum);
}
}
return 0;
}
最後更新：2017-04-03 12:56:01