【UOJ 51】最接近神的人

【题目描述】：

破解了符文之语，小FF开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小FF猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……

仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。

小FF发现门上同样有着n个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小FF不会……只好又找到了你，并答应事成之后与你三七分……

【输入描述】：

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。

【输出描述】：

给定序列的最少操作次数。

【样例输入】：

6
5 4 2 6 3 1

【样例输出】：

11

【时间限制、数据范围及描述】：

时间：1s 空间：128M

对于50%的数据，n<=2500

对于100%的数据，n<=40000。

-maxlongint<=ai<=maxlongint

题解：emm

using namespace std;const int N=1000005;
int t,n,aa[N],c[N],i,ans;struct Node{int v; int order;
}a[N];bool cmp(Node a,Node b){return a.v<b.v;
}int lowbit(int k){return k&(-k);
}void update(int t, int value){int i;for(i=t;i<=n;i+=lowbit(i)){c[i]+=value;}
}int getsum(int t){int i,sum=0;for(i=t;i>=1;i-=lowbit(i)){sum+=c[i];}return sum;
}int main(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].order=i;}stable_sort(a+1,a+1+n,cmp);for(i=1;i<=n;i++){aa[a[i].order]=i;}for(i=1;i<=n;i++){update(aa[i],1);ans+=i-getsum(aa[i]);}printf("%d\n",ans);return 0;
}

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11196321.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！