微软2014实习生及秋令营技术类职位在线测试-题目3 : Reduce inversion count

 这道题有几个关键的地方：
1、计算一个数组的逆序对的个数。
　　我采用遍历的方式，用两重循环，时间复杂度O(N^2)，应该没有效率更高的方法【代码27-32】；
2、找到一对(d[j],d[k],设j<k)，通过交换他们，可以使得逆序对数减少最多。
　　首先看下交换任意一对(d[j],d[k]，设j<k),会对这个数组的逆序对的个数造成什么样的影响。认真思考下，可以知道交换(d[j],d[k])只影响在j到k之间的元素的逆序情况，而对这个范围之外的逆序对的个数是不造成影响的，因为[0到j-1]的任意元素相对[j到k]的任意元素的先后顺序，以及[k到len-1]的任意元素相对[j到k]的任意元素的先后顺序都没有变化。那么就只需要考虑交换后[i到j]之间逆序对变化的个数。交换(d[j],d[k])后，减少的逆序对是由下标在[j,k)之间且其元素大于d[k],以及下标在(j,k]之间且其元素小于d[j]，而增加的逆序对是由下标在[j,k)之间且其元素小于d[k],以及下标在(j,k]之间且其元素大于d[j]【代码41-51】。另外一个值得注意的是只有当d[k]<d[j]时，交换才能减少逆序对数。
 1 #include<stdio.h>
int main(void)
{
    char data[120];
    int len = 0;
    int d[50];
    int j =0,k=0,l =0,i=0;
    int cnt =0,max =0,x=0,y=0,n=0;
    while(gets(data))
    {
        len = 0;
        i =0;
        j = 0;
        cnt =0,max =0;;
        n=0;
        //operate input
        while(data[i]!='')
        {
            if(data[i]!=',')
            {
                d[j++] = data[i]-'0';
                len++;
            }
            i++;
        }
        //count orignal reversion pairs
        for(j=0;j<len;j++)
        {
            for(k=j+1;k<len;k++)
                if(d[j]>d[k])
                    cnt++;
        }
        //FIND the right pair which can largest reduce the count
        for(j=0;j<len-1;j++)
        {
            for(k=j+1;k<len;k++)
            {
                n=0;
                if(d[k]>d[j])
                    continue;
                for(l=j;l<k;l++)
                {
                    if(d[l]>d[j])
                        n--;
                    if(d[l]<d[j])
                        n++;
                    if(d[l]>d[k])
                        n++;
                    if(d[l]<d[k])
                        n--;
                }
                if(n>max)
                    max = n;
            }
        }

        printf("%d
",cnt-max);

    }
    return 0;
}
最后声明下，作为菜鸟一个，没有在给定时间里，完整的把代码中的几个条件考虑进去，因此这里的程序不知道是否可以AC，但是我跑些case的结果是对的。