首页 > ACM题库 > HDU-杭电 > HDU 4137-Manhattan Sort-贪心-[解题报告]HOJ
2015
04-16

HDU 4137-Manhattan Sort-贪心-[解题报告]HOJ

Manhattan Sort

问题描述 :

Yet another sorting problem! In this one, you’re given a sequence S of N distinct integers and are asked to sort it with minimum cost using only one operation:
The Manhattan swap!
Let Si and Sj be two elements of the sequence at positions i and j respectively, applying the Manhattan swap operation to Si and Sj swaps both elements with a cost of |i-j|. For example, given the sequence {9,5,3}, we can sort the sequence with a single Manhattan swap operation by swapping the first and last elements for a total cost of 2 (absolute difference between positions of 9 and 3).

输入:

The first line of input contains an integer T, the number of test cases. Each test case consists of 2 lines. The first line consists of a single integer (1 <= N <= 30), the length of the sequence S. The second line contains N space separated integers representing the elements of S. All sequence elements are distinct and fit in 32 bit signed integer.

输出:

The first line of input contains an integer T, the number of test cases. Each test case consists of 2 lines. The first line consists of a single integer (1 <= N <= 30), the length of the sequence S. The second line contains N space separated integers representing the elements of S. All sequence elements are distinct and fit in 32 bit signed integer.

样例输入:

2
3
9 5 3
6
6 5 4 3 2 1

样例输出:

Case #1: 2
Case #2: 9

咋一看,Manhattan Sort?纳尼?其实水题一道…运用了贪心,因为要总的移动的距离最小的最优办法就是直接把它挪到它应该放的地方,况且每个数都是唯一的

struct node{
    int id;
    int v;
}p[33];
bool cmp(node a,node b){
    return a.v<b.v;
}
int main(){
    int t;
    scanf("%d",&t);
    int ca=1;
    while(t--){
        int n;
        scanf("%d",&n);
        int i;
        int ans = 0;
        for(i=1;i<=n;i++){
            scanf("%d",&p[i].v);
            p[i].id = i;
        }
        sort(p+1,p+1+n,cmp);
        for(i=1;i<=n;i++){
            ans += abs(p[i].id-i);
        }
        printf("Case #%d: %d\n",ca++,ans/2);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/leolin_/article/details/7304326