2014-01-24 10:51:37| 人氣2,318| 回應0 | 上一篇 | 下一篇

[UVA][greedy] 10570 - Meeting with Aliens

推薦 0 收藏 0 轉貼0 訂閱站台

Problem D
Meeting with Aliens
Input: Standard Input

Output: Standard Output

Time Limit: 3 Seconds

The aliens are in an important meeting just before landing on the earth. All the aliens sit around a round table during the meeting. Aliens are numbered sequentially from 1 to N. It's a precondition of the meeting that i'th alien will sit between (i-1)'th and (i+1)'th alien. 1st alien will sit between 2nd and N'th alien.

Though the ordering of aliens are fixed but their positions are not fixed. In the above figure two valid sitting arrangements of eight aliens are shown. Right before the start of the meeting the aliens sometimes face a common problem of not maintaining the proper order. This occurs as no alien has a fixed position. Two maintain the proper order, two aliens can exchange their positions. The aliens want to know the minimum number of exchange operations necessary to fix the order.

Input

Input will start with a positive integer, N (3<=N<=500) the number of aliens. In next few lines there will be N distinct integers from 1 to N indicating the current ordering of aliens. Input is terminated by a case where N=0. This case should not be processed. There will be not more than 100 datasets.

Output

For each set of input print the minimum exchange operations required to fix the ordering of aliens.

Sample Input Output for Sample Input

1 2 3 4

4 3 2 1

2 3 1 4

題目描述：

外星人圍一桌，現在要調整位置，使得成為有序的環狀。
可以任意交換兩個人的位置，求最少操作數。

題目解法：

對於 n 個數字，調整成由大到小或者是由小到大，操作數不超過 n。
每一次操作至少要將一個數字歸位。

窮舉由大到小或者是由小到大，然後窮舉環狀的有序起始位置。

接著使用 greedy 找到排序的最少操作次數。

#include <stdio.h>
#include <algorithm>
using namespace std;
int solve(int n, int a[]) {
   int b[1005];
   int ret = 0xfffffff;
   int i, j, k;
   for(i = 0, j = n; i < n; i++, j++)
        a[j] = a[i];
   for(i = 0; i < n; i++) {
        int mark[505], cnt = 0;
        for(j = 0; j < n; j++) {
            mark[a[i+j]] = i+j;
            b[i+j] = a[i+j];
        }
        for(j = 0; j < n; j++) {
            if(b[i+j] != j) {
                cnt++;
                int idx = mark[j];
                swap(b[i+j], b[idx]);
                mark[b[idx]] = idx;
            }
        }
        ret = min(ret, cnt);
   }
   return ret;
}
int main() {
   int n, i, j, k;
   int a[1005];
   while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            a[i]--;
        }
        int ret;
        ret = solve(n, a);
        reverse(a, a+n);
        ret = min(ret, solve(n, a));
        printf("%d\n", ret);
   }
   return 0;
}

我要檢舉

#10570#Meeting with Aliens

台長： Morris

您可能對以下文章有興趣

[UVA][Trie] 12526 - Cellphone Typing

[UVA][dp][2DLIS] 1196 - Tiling Up Blocks

[ACM-ICPC][Asia - Seoul][Farthest Pair] 4728 - Squares

[UVA][匈牙利] 11363 - Cuckoo Hashing

人氣(2,318) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 10560 - Minmum Weight
此分類上一篇:[UVA][樹形dp] 10859 - Placing Lampposts

回應(0)