首页 > 代码库 > 小朋友排队--第五届蓝桥杯

小朋友排队--第五届蓝桥杯

第一种,直接思考的方法,不知对不正确:

/*
 * 标题:小朋友排队
 n 个小朋友站成一排。如今要把他们按身高从低到高的顺序排列,可是每次仅仅能交换位置相邻的两个小朋友。

每一个小朋友都有一个不高兴的程度。

開始的时候。全部小朋友的不高兴程度都是0。 假设某个小朋友第一次被要求交换,则他的不高兴程度添加1,假设第二次要求他交换。 则他的不高兴程度添加2(即总的不高兴程度为3)。依次类推。

当要求某个小朋友第k次交换时,他的不高兴程度添加k。 请问。要让全部小朋友按从低到高排队。他们的不高兴程度之和最小是多少。 假设有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。 【数据格式】 输入的第一行包括一个整数n,表示小朋友的个数。 第二行包括 n 个整数 H1 H2 … Hn,分别表示每一个小朋友的身高。 输出一行,包括一个整数,表示小朋友的不高兴程度和的最小值。 比如,输入: 3 3 2 1 程序应该输出: 9 【例子说明】 首先交换身高为3和2的小朋友,再交换身高为3和1的小朋友,再交换身高为2和1的小朋友,每一个小朋友的不高兴程度都是3。总和为9。 【数据规模与约定】 对于10%的数据, 1<=n<=10; 对于30%的数据, 1<=n<=1000。 对于50%的数据。 1<=n<=10000; 对于100%的数据,1<=n<=100000,0<=Hi<=1000000。 资源约定: 峰值内存消耗 < 256M CPU消耗 < 1000ms */ public class 小朋友排队 { static int n; static int[] s;// 每一个小朋友的身高 static int bugaoxing = 99999;// 不高兴的值总和 /** * 当前最高兴的小朋友的值总的高兴值 */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); s = new int[n]; int[][] count = new int[n][2]; for (int i = 0; i < n; i++) { s[i] = sc.nextInt(); count[i][0] = 0; count[i][1] = 0; } long start = System.currentTimeMillis(); int all = exchange(findMin(count), count); print("不高兴的总和数量是=" + all); long end = System.currentTimeMillis(); print("此程序执行,花费的时间是" + ((end - start) / 1000.0) + "秒."); print("每一个小朋友不高兴的详情信息"); for (int i = 0; i < n; i++) { print(i + "不高兴的值是=" + count[i][0]); } } /** * 交换位置,身高高的向右和身高低的能够换,否则下一个相邻位置 * * @param k * 前搜索的位置 * @param count * count[0][]当前每一个交换的小朋友的不高兴程度和count[1][]交换的次数 */ public static int exchange(int k, int[][] count) { if (isOk()) { int temp = sum(count); if (temp < bugaoxing) bugaoxing = temp; return temp; } else { /** 交换身高,从最不高兴的到最高兴的意思搜索 */ exchangeAll(count, k); System.out.println("K&k+1=" + k + " " + (k + 1)); return exchange(findMin(count), count); } } /** * * @return 返回当前相对最高兴的小朋友的下标值,(同事满足身高左高右低的要求) */ public static int findMin(int[][] count) { int[] temp = new int[n]; for (int i = 0; i < n; i++) { temp[i] = count[i][1]; } for (int i = 0; i < n; i++) { int min = i; for (int j = i + 1; j < n; j++) { if (temp[min] > temp[j]) min = j; } temp[min] = temp[i]; if (min < n - 1 && s[min] > s[min + 1]) return min; } return n - 2; } /** * 交换位置和不高兴的值下标k和k+1的交换,同一时候不高兴的值添加 * * @return */ public static void exchangeAll(int[][] count, int k) { int temp; temp = s[k + 1]; s[k + 1] = s[k]; s[k] = temp; count[k][1]++; count[k][0] = count[k][0] + count[k][1]; count[k + 1][1]++; count[k + 1][0] = count[k + 1][0] + count[k + 1][1]; int[] temp1 = count[k]; count[k] = count[k + 1]; count[k + 1] = temp1; } public static boolean isOk() {// 是否排好序 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (s[j] < s[i]) return false; } } return true; } // 当前全部人不高兴的值的总和 public static int sum(int[][] count) { int temp = 0; for (int i = 0; i < n; i++) temp += count[i][0]; return temp; } public static void print(Object o) { System.out.println(o.toString()); } }



输入和输出一:

3
3 2 1
K&k+1=0   1
K&k+1=1   2
K&k+1=0   1
不高兴的总和数量是=9
每一个小朋友不高兴的详情信息
0不高兴的值是=3
1不高兴的值是=3
2不高兴的值是=3
此程序执行,花费的时间是0.0秒.

输入和输出二:

5
5 4 3 2 1
K&k+1=0   1
K&k+1=2   3
K&k+1=1   2
K&k+1=3   4
K&k+1=0   1
K&k+1=2   3
K&k+1=1   2
K&k+1=3   4
K&k+1=0   1
K&k+1=2   3
不高兴的总和数量是=50
每一个小朋友不高兴的详情信息
0不高兴的值是=10
1不高兴的值是=10
2不高兴的值是=10
3不高兴的值是=10
4不高兴的值是=10
此程序执行,花费的时间是0.001秒.


输入和输出三:

5
2 5 4 3 1
K&k+1=1   2
K&k+1=3   4
K&k+1=2   3
K&k+1=1   2
K&k+1=0   1
K&k+1=3   4
K&k+1=2   3
不高兴的总和数量是=29
此程序执行,花费的时间是0.0秒.
每一个小朋友不高兴的详情信息
0不高兴的值是=10
1不高兴的值是=1
2不高兴的值是=6
3不高兴的值是=6
4不高兴的值是=6


小朋友排队--第五届蓝桥杯