首先声明,我是一个菜鸟。一下文章中出现技术误导情况盖不负责
尝试用线段树去写,但是始终不能完全弄清标题的意思,干脆就用暴力先过一遍,再去纠结怎么用线段树过。
想了想还是加一下注释,因为数列由0到n-1这n个数组成,那么将x一道序列末尾的时候,发生的新的序列的逆序数是原序列逆序数加上n-x-1,再减去x。
#include<stdio.h> int Min(int x,int y) { return x<y?x:y; } int main() { int n; int a[5005]; int i,j,ans,sum; while(scanf("%d",&n)!=EOF) { for(i=0; i<n; i++) scanf("%d",&a[i]); ans=99999999; sum=0; for(i=0; i<n; i++) { for(j=i+1; j<n; j++) { if(a[i]>a[j]) sum++; } } for(i=0; i<n-1; i++) { sum=sum+n-a[i]-a[i]-1; ans=Min(ans,sum); } printf("%d\n",ans); } return 0; }
文章结束给大家分享下程序员的一些笑话语录: 自行车
一个程序员骑着一个很漂亮的自行车到了公司,另一个程序员看到了他,问 到,“你是从哪搞到的这么漂亮的车的?”
骑车的那个程序员说, “我刚从那边过来, 有一个漂亮的姑娘骑着这个车过来, 并停在我跟前,把衣服全脱了,然后对我说,‘你想要什么都可以’”。
另一个程序员马上说到, “你绝对做了一个正确的选择, 因为那姑娘的衣服你 并不一定穿得了”。