小朋友排隊(duì)

n 個(gè)小朋友站成一排。現(xiàn)在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個(gè)小朋友。
每個(gè)小朋友都有一個(gè)不高興的程度。開(kāi)始的時(shí)候，所有小朋友的不高興程度都是0。
如果某個(gè)小朋友第一次被要求交換，則他的不高興程度增加1，如果第二次要求他交換，則他的不高興程度增加2（即不高興程度為3），依次類推。當(dāng)要求某個(gè)小朋友第k次交換時(shí)，他的不高興程度增加k。
請(qǐng)問(wèn)，要讓所有小朋友按從低到高排隊(duì)，他們的不高興程度之和最小是多少。
如果有兩個(gè)小朋友身高一樣，則他們誰(shuí)站在誰(shuí)前面是沒(méi)有關(guān)系的。
【數(shù)據(jù)格式】
輸入的第一行包含一個(gè)整數(shù)n，表示小朋友的個(gè)數(shù)。 第二行包含 n 個(gè)整數(shù) H1 H2 … Hn，分別表示每個(gè)小朋友的身高。 輸出一行，包含一個(gè)整數(shù)，表示小朋友的不高興程度和的最小值。
例如，輸入：
3
3 2 1
程序應(yīng)該輸出：
9
【樣例說(shuō)明】 首先交換身高為3和2的小朋友，再交換身高為3和1的小朋友，再交換身高為2和1的小朋友，每個(gè)小朋友的不高興程度都是3，總和為9。
【數(shù)據(jù)規(guī)模與約定】 對(duì)于10%的數(shù)據(jù)， 1<=n<=10； 對(duì)于30%的數(shù)據(jù)， 1<=n<=1000； 對(duì)于50%的數(shù)據(jù)， 1<=n<=10000； 對(duì)于100%的數(shù)據(jù)，1<=n<=100000，0<=Hi<=1000000。
資源約定： 峰值內(nèi)存消耗 < 256M CPU消耗 < 1000ms
請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入...” 的多余內(nèi)容。
所有代碼放在同一個(gè)源文件中，調(diào)試通過(guò)后，拷貝提交該源碼。
注意: main函數(shù)需要返回0 注意: 只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。 注意: 所有依賴的函數(shù)必須明確地在源文件中 #include ， 不能通過(guò)工程設(shè)置而省略常用頭文件。
提交時(shí)，注意選擇所期望的編譯器類型。

思路一：求逆序?qū)?#xff1a;左邊大于它的 + 右邊小于它的數(shù)量，求完逆序?qū)?計(jì)算等差數(shù)列和 (因?yàn)椴桓吲d程度每次增加k)

待改進(jìn)：只能過(guò)50%的數(shù)據(jù)，超時(shí)了。需要用歸并排序 和 樹(shù)狀數(shù)組改進(jìn)。

#include<iostream> using namespace std;int n; int arr[1000010]; long long ans = 0;/* 求逆序?qū)?#xff1a;左邊大于它的 + 右邊小于它的數(shù)量 求完逆序?qū)?計(jì)算等差數(shù)列和 (因?yàn)椴桓吲d程度每次增加k) */ long long cal(long long x){return x + x*(x-1)/2; }int main(){cin>>n;for(int i=1;i<=n;i++){cin>>arr[i];}for(int i=1;i<=n;i++){long long ans1 = 0;long long ans2 = 0;for(int j=1;j<i;j++){if(arr[j] > arr[i]){ans1++;}}for(int j=i+1;j<=n;j++){if(arr[j]<arr[i]){ans2++;}}ans+=cal(ans1 + ans2); }cout<<ans<<endl; }

代碼：

#include <iostream> #include <cstdio> #define _for(i,a,b) for(int i=a;i<b;i++) #define _unfor(i,a,b) for(int i=a;i>=b;i--) #define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val; #define lowbit(x) (x&(-x)) using namespace std; typedef long long LL;int a[100005],d[1000005],n,lr[100005],maxh=0; //tree_arrvoid add(int i,int x){while(i<=maxh+1)d[i]+=x,i+=lowbit(i);}int sum(int i){int res=0;while(i>0)res+=d[i],i-=lowbit(i);return res;} // int main(){scanf("%d",&n);_for(i,0,n){scanf("%d",&a[i]);maxh=max(maxh,++a[i]);}_for(i,0,n){add(a[i],1);lr[i]+=i+1-sum(a[i]);}mset(d,0,maxh+5);_unfor(i,n-1,0){add(a[i],1);lr[i]+=sum(a[i]-1);}LL ans=0;_for(i,0,n){LL k=lr[i];ans+=k*(k+1)/2;}cout<<ans<<endl; }

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

總結(jié)

以上是生活随笔為你收集整理的小朋友排队|2014年蓝桥杯B组题解析第十题-fishers的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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