?

題目描述

破解了符文之語，小FF開啟了通往地下的道路。當(dāng)他走到最底層時(shí)，發(fā)現(xiàn)正前方有一扇巨石門，門上雕刻著一幅古代人進(jìn)行某種活動(dòng)的圖案。而石門上方用古代文寫著“神的殿堂”。小FF猜想里面應(yīng)該就有王室的遺產(chǎn)了。但現(xiàn)在的問題是如何打開這扇門……

仔細(xì)研究后，他發(fā)現(xiàn)門上的圖案大概是說：古代人認(rèn)為只有智者才是最容易接近神明的。而最聰明的人往往通過一種儀式選拔出來。儀式大概是指，即將隱退的智者為他的候選人寫下一串無序的數(shù)字，并讓他們進(jìn)行一種操作，即交換序列中相鄰的兩個(gè)元素。而用最少的交換次數(shù)使原序列變成不下降序列的人即是下一任智者。

小FF發(fā)現(xiàn)門上同樣有著n個(gè)數(shù)字。于是他認(rèn)為打開這扇門的秘訣就是找到讓這個(gè)序列變成不下降序列所需要的最小次數(shù)。但小FF不會(huì)……只好又找到了你，并答應(yīng)事成之后與你三七分……

輸入輸出格式

輸入格式：

?

第一行為一個(gè)整數(shù)n，表示序列長度

第二行為n個(gè)整數(shù)，表示序列中每個(gè)元素。

?

輸出格式：

?

一個(gè)整數(shù)ans，即最少操作次數(shù)。

?

輸入輸出樣例

輸入樣例#1：
4 2 8 0 3 輸出樣例#1：
3樣例說明：開始序列為2 8 0 3，目標(biāo)序列為0 2 3 8，可進(jìn)行三次操作的目標(biāo)序列：1．Swap (8,0):2 0 8 32．Swap (2,0):0 2 8 33．Swap (8,3):0 2 3 8

說明

對于30%的數(shù)據(jù)1≤n≤10^4。

對于100%的數(shù)據(jù)1≤n≤5*10^5；

-maxlongint≤A[i]≤maxlongint。

?

?歸并排序求逆序?qū)?#xff1a; #include<iostream> #include<cstdio> #include<algorithm> #define ll long long intusing namespace std; const ll N=500010;ll a[N]; ll ans[N]; ll answer; ll n; ll now;ll read() {ll x=0;char c=getchar();ll f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f; }void T_S(ll start,ll endd) {if(start==endd)return ;int mid=(start+endd)/2;T_S(start,mid);T_S(mid+1,endd);ll i=start,j=mid+1;now=start;while(i<=mid&&j<=endd)if(a[i]<=a[j])ans[now++]=a[i++];elseanswer+=mid-i+1,ans[now++]=a[j++];while(i<=mid)ans[now++]=a[i++];while(j<=endd)ans[now++]=a[j++];for(int i=start;i<=endd;i++)a[i]=ans[i]; }int main() {n=read();for(int i=1;i<=n;i++)a[i]=read();T_S(1,n);printf("%lld",answer);return 0; }

?

?樹狀數(shù)組求逆序?qū)?#xff08;較慢）： #include<bits/stdc++.h>using namespace std; const int maxn=1e6+7; int n; int sz[maxn],c[maxn]; struct node {int dat,pos; }nd[maxn];bool cmp(node a,node b) {return a.dat<b.dat; } inline int lowbit(int x) {return x&(-x); } int getsum(int x) {int sum=0;for(;x>0;x-=lowbit(x))sum+=c[x];return sum; } void updat(int x) {for(;x<=n;x+=lowbit(x))c[x]++; } int main() {cin>>n;for(int i=1;i<=n;i++){scanf("%d",sz+i);nd[i].dat=sz[i];nd[i].pos=i;}sort(nd+1,nd+1+n,cmp);int js=1;sz[nd[1].pos]=1;for(int i=2;i<=n;i++){if(nd[i].dat==nd[i-1].dat)sz[nd[i].pos]=js;else sz[nd[i].pos]=++js;}long long ans=0;for(int i=1;i<=n;i++){ans+=i-getsum(sz[i])-1;//<=sz[i] updat(sz[i]);}cout<<ans;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lyqlyq/p/7100724.html

總結(jié)

以上是生活随笔為你收集整理的luogu P1774 最接近神的人_NOI导刊2010提高（02）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。