2017-8-7

題目描述

給定的一個(gè)1,2,3組成的數(shù)字序列，排成升序所需的最少交換次數(shù)

解答

將結(jié)果與所給情況進(jìn)行比較，相等不用處理，對(duì)應(yīng)相反直接交換即可，否則進(jìn)行處理

代碼

/* ID: 18795871 PROG: sort3 LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> using namespace std; const int N = 1000;ifstream fin("sort3.in"); ofstream fout("sort3.out");int x[N+1],y[N+1]; bool f[N+1]; int cnt=0,n,x1,x2,x3;void init(){int i;for (i=1;i<=x1;i++) y[i]=1;for (i=x1+1;i<=x1+x2;i++) y[i]=2;for (i=x1+x2+1;i<=x1+x2+x3;i++) y[i]=3; }void cal(){int i,j;int ss=0;for (i=1;i<=n;i++){if (x[i]==y[i]) f[i]=true;}for (i=1;i<=n;i++){if (!f[i]){for (j=i+1;j<=n;j++){if (!f[j]&&x[i]==y[j]&&x[j]==y[i]){ //對(duì)應(yīng)相反直接交換 cnt++;f[i]=true;f[j]=true;break;}}}}int s=0;for (i=1;i<=n;i++){if (!f[i]) s++;}if (s!=0) fout<<s/3*2+cnt<<endl;else fout<<cnt<<endl; }int main() {fin>>n;x1=0,x2=0,x3=0;for (int i=1;i<=n;i++){fin>>x[i];if (x[i]==1) x1++;else if (x[i]==2) x2++;else x3++;}init();cal();return 0; } 新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的USACO-Section2.1 Sorting a Three-Valued Sequence（排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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