您所在位置：主题：[讨论]ACM牛人的进来,一道恶心我的题目
powerforever
[专家分：30] 发布于 2010-09-06 20:45:00
题目如下：
SuperRock和诺曼底登陆
Submit: 463 Accepted:156
Time Limit: 1000MS Memory Limit: 65536K
Description
这是一个有关于诺曼底登陆战中军官SuperRock中校的故事。SuperRock中校手下有 N（1 <= N <= 10,000）个士兵。可是他们的脾气都不好，脾气大的士兵有可能会捣乱。聪明的SuperRock中校打算把士兵按脾气的大小排排队。每一个士兵的脾气都是一个在1到100，000之间的整数并且没有两个士兵的脾气值相同。在排序过程中，SuperRock可以交换任意两个士兵的位置。因为脾气大的士兵不好移动，SuperRock需要X+Y秒来交换脾气值为X和Y的两个士兵。
时间已经差不多了，尽管SuperRock还是一个不错的程序爱好者，可是他的笔记本坏了，来不及修好。作为有天赋的而且热心的编程高手,请你帮SuperRock计算把所有士兵排好序的最短时间.
Input
第1行： 一个数， N。
第2~N+1行： 每行一个数，第i+1行是第i个士兵的脾气值
Output
第1行： 一个数，把所有士兵排好序的最短时间。
Sample Input
3
2
3
1
Sample Output
7
Hint
输入解释：
队列里有三个士兵，脾气分别为 2，3， 1。
输出解释：
2 3 1 : 初始序列
2 1 3 : 交换脾气为3和1的士兵(时间=1+3=4).
1 2 3 : 交换脾气为1和2的士兵(时间=2+1=3).
Source
Moyuji@Bupt
我做了提交过就是WA，但我认为我的算法没有问题！2个小时后我会发我的代码，先求高手赐教！谢了，牛人门！！
SuperRock和诺曼底登陆
Submit: 463 Accepted:156
Time Limit: 1000MS Memory Limit: 65536K
Description
这是一个有关于诺曼底登陆战中军官SuperRock中校的故事。SuperRock中校手下有 N（1 <= N <= 10,000）个士兵。可是他们的脾气都不好，脾气大的士兵有可能会捣乱。聪明的SuperRock中校打算把士兵按脾气的大小排排队。每一个士兵的脾气都是一个在1到100，000之间的整数并且没有两个士兵的脾气值相同。在排序过程中，SuperRock可以交换任意两个士兵的位置。因为脾气大的士兵不好移动，SuperRock需要X+Y秒来交换脾气值为X和Y的两个士兵。
时间已经差不多了，尽管SuperRock还是一个不错的程序爱好者，可是他的笔记本坏了，来不及修好。作为有天赋的而且热心的编程高手,请你帮SuperRock计算把所有士兵排好序的最短时间.
Input
第1行： 一个数， N。
第2~N+1行： 每行一个数，第i+1行是第i个士兵的脾气值
Output
第1行： 一个数，把所有士兵排好序的最短时间。
Sample Input
3
2
3
1
Sample Output
7
Hint
输入解释：
队列里有三个士兵，脾气分别为 2，3， 1。
输出解释：
2 3 1 : 初始序列
2 1 3 : 交换脾气为3和1的士兵(时间=1+3=4).
1 2 3 : 交换脾气为1和2的士兵(时间=2+1=3).
Source
Moyuji@Bupt
我做了提交过就是WA，但我认为我的算法没有问题！2个小时后我会发我的代码，先求高手赐教！谢了，牛人门！！