网站品牌建设,上海上咨建设工程咨询有限公司,横向网站模板,十大接单推广app平台题目描述 破解了符文之语#xff0c;小FF开启了通往地下的道路。当他走到最底层时#xff0c;发现正前方有一扇巨石门#xff0c;门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小FF猜想里面应该就有王室的遗产了。但现在的问题是如何打开这… 题目描述 破解了符文之语小FF开启了通往地下的道路。当他走到最底层时发现正前方有一扇巨石门门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小FF猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门…… 仔细研究后他发现门上的图案大概是说古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指即将隐退的智者为他的候选人写下一串无序的数字并让他们进行一种操作即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。 小FF发现门上同样有着n个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小FF不会……只好又找到了你并答应事成之后与你三七分…… 输入输出格式 输入格式 第一行为一个整数n表示序列长度 第二行为n个整数表示序列中每个元素。 输出格式 一个整数ans即最少操作次数。 输入输出样例 输入样例#14
2 8 0 3输出样例#13样例说明开始序列为2 8 0 3目标序列为0 2 3 8可进行三次操作的目标序列1Swap (8,0):2 0 8 32Swap (2,0):0 2 8 33Swap (8,3):0 2 3 8说明 对于30%的数据1≤n≤10^4。 对于100%的数据1≤n≤5*10^5 -maxlongint≤A[i]≤maxlongint。 归并排序求逆序对 #includeiostream
#includecstdio
#includealgorithm
#define ll long long intusing namespace std;
const ll N500010;ll a[N];
ll ans[N];
ll answer;
ll n;
ll now;ll read()
{ll x0;char cgetchar();ll f1;while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9)xx*10c-0,cgetchar();return x*f;
}void T_S(ll start,ll endd)
{if(startendd)return ;int mid(startendd)/2;T_S(start,mid);T_S(mid1,endd);ll istart,jmid1;nowstart;while(imidjendd)if(a[i]a[j])ans[now]a[i];elseanswermid-i1,ans[now]a[j];while(imid)ans[now]a[i];while(jendd)ans[now]a[j];for(int istart;iendd;i)a[i]ans[i];
}int main()
{nread();for(int i1;in;i)a[i]read();T_S(1,n);printf(%lld,answer);return 0;
} 树状数组求逆序对较慢 #includebits/stdc.husing namespace std;
const int maxn1e67;
int n;
int sz[maxn],c[maxn];
struct node
{int dat,pos;
}nd[maxn];bool cmp(node a,node b)
{return a.datb.dat;
}
inline int lowbit(int x)
{return x(-x);
}
int getsum(int x)
{int sum0;for(;x0;x-lowbit(x))sumc[x];return sum;
}
void updat(int x)
{for(;xn;xlowbit(x))c[x];
}
int main()
{cinn;for(int i1;in;i){scanf(%d,szi);nd[i].datsz[i];nd[i].posi;}sort(nd1,nd1n,cmp);int js1;sz[nd[1].pos]1;for(int i2;in;i){if(nd[i].datnd[i-1].dat)sz[nd[i].pos]js;else sz[nd[i].pos]js;}long long ans0;for(int i1;in;i){ansi-getsum(sz[i])-1;//sz[i]updat(sz[i]);}coutans;return 0;
} 转载于:https://www.cnblogs.com/lyqlyq/p/7100724.html
