hdunbsp;1394

解题报告

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1394

题目大意：给定序列，序列可变换即将前面i个移到序列后边，问经过变换可得到的最小的逆序数是多少？

思路：最近状态一塌糊涂啊，一开始居然连怎样利用求和的思想去就逆序数都不会了，想了半天也没想起来，看了看别人的解题报告才又一次恍然大悟，就是记录每个数字在他之前一共出现了多少个比他小的数，这样用它出现的时刻减去前面出现的比他小的数，剩下的就是比他大的，也就是由他导致的逆序数的个数，然后将这些数加起来。然后题目又是让求所有变换中的最小的，一想这样的题目肯定变换有递推公式，于是想了半天记录每个数之前比他小，之后比他大之类的信息，最后发现还是推不出来，于是没办法由又去看别人怎么说，一看又恍然大悟，每次都是相当于将最顶头的数拿到最后边，这是这个问题最关键独特的地方啊，居然没有注意到，编程珠玑真是白看了。注意到了这一点，递推公式也就好推了。

收获与体会：要赶紧找回感觉了。

AC code：

#include <cstdio>

#include <cstring>

#define MAXN 5010

int tray[MAXN], data[MAXN];

void Updata(int start, int C, intlimit){

    for(int i = start; i <limit; i += i & -i) tray[i]+= C;

}

int Getsum(int start, int limit){

    int ans = 0;

    for(int i = start; i >limit; i -= i & -i) ans +=tray[i];

    return ans;

}

int main(){

    int n, ans, now;

    while(~scanf("%d", &n)){

       memset(tray, 0, sizeof(tray));

       ans = 0;

       for(int i = 1; i <=n; ++ i){

           scanf("%d",&data[i]);

           Updata(data[i] + 1,1, n + 1);

           ans += i -Getsum(data[i] + 1, 0);

       }

       now = ans;

       for(int i = 1; i <=n; ++ i){

           now = now +(n - 2 * data[i] - 1);

           if(now < ans) ans = now;

       }

       printf("%d\n",ans);

    }

    return 0;

}