【题目描述】

农场里的马，在草场开心地吃着牧草，直到天色晚了，牧马的人会将马依次按号牌大小，依次放入相应的位置。

但是这马总是打乱了顺序，于是牧马人都会想办法把这些马都排好：每次从最前面开始，然后与后面的号牌进行比较，每次将小的号牌的马换到前面。这牧马人整理马的顺序相当耗费体力，每次交换，消耗体力为两匹马槽位的距离*2。他想知道，他要花费多少体力才能完成任务。

【输入描述】

第一行是一个整数n(n<3000)代表马的个数

接下来一行，共n个数，代表马的编号

【输出描述】

一个数，表示花费的体力。

【样例输入】

6  2 3 6 5 8 4

【样例输出】 

14

【题目分析】

• 实际上是冒泡排序的简单改版，类似于求解交换了多少次

• 题目中“每次从最前面开始，然后与后面的号牌进行比较，每次将小的号牌的马换到前面。”这句是最关键的

• 注意每次从最前面开始。

• 每次将小的号牌的马换到前面。这个最麻烦，题目中只说小的号牌，并没有说最小的号牌，也就是从头开始比较，遇到比我小的就交换。

• “马槽”就是当前马的位置

首先回顾一下冒泡排序的过程，再回来看到底有哪些不一样的地方。冒泡排序过程点击这里。

【过程分解】

初始状态： 2  3  6  5  8   4 

第一轮：    2  3  5  6  8   4

第二轮：    2  3  4  6  8   5

第三轮：    2  3  4  5  8   6 

第四轮：    2  3  4  5  6   8

解释：从初始状态到第一轮，因为从头开始，所以2和3 后面没有比他们俩还小的数字，6后面有两个比6小的数字有两个，5和4，4最小，但是题目中只说比6小的，也就就近原则，所以应该是5和6交换，这就是为什么很多人算不出来答案的主要原因。体力=1*2=2

从第一轮到第二轮，还是没有比 2和3还小的数，比5小的数只有4，然后两个交换，体力=3*2=6。

从第二轮到第三轮，没有比2、3、4还小的数字，比6小的数字只有5，然后两个交换，体力=2*2=4。

从第三轮到第四轮，没有比2，3，4，5还小的数字，比8小的只有6，然后两个交换，体力=1*2=2。

最后的总体力=2+6+4+2=14。

【参考答案】

#include<iostream>   using namespace std;  int a[3000]; //存数的数组   int main(){      int n;      cin>>n;      for(int i=1;i<=n;i++){          cin>>a[i];      }      int p,sum=0;      for(int i=1;i<=n;i++){          for(int j=i+1;j<=n;j++){              if(a[i]>a[j]){  //遇到比自己小的                  swap(a[i],a[j]); //交换                  sum+=(j-i)*2;  //下标之差的两倍就是体力               }          }      }      cout<<sum;      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});