首页 > 代码库 > Sorting a Three-Valued Sequence
Sorting a Three-Valued Sequence
链接
分析:首先我们先对其进行排序,并看排序以后有多少个元素顺序是对的,接着我们看有多少个元素经过一次交换可以得到的,最后剩下的元素就是经过两次交换可以得到的了。
1 /* 2 PROB:sort3 3 ID:wanghan 4 LANG:C++ 5 */ 6 #include "iostream" 7 #include "cstdio" 8 #include "cstring" 9 #include "string" 10 #include "algorithm" 11 using namespace std; 12 const int maxn=1000+10; 13 int a[maxn],b[maxn]; 14 int vis[maxn]; 15 int n; 16 int main() 17 { 18 freopen("sort3.in","r",stdin); 19 freopen("sort3.out","w",stdout); 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++){ 22 cin>>a[i]; 23 b[i]=a[i]; 24 } 25 sort(b+1,b+1+n); 26 for(int i=1;i<=n;i++){ 27 if(a[i]==b[i]){ 28 vis[i]=1; 29 } 30 } 31 int cnt=0; 32 for(int i=1;i<=n-1;i++){ 33 if(!vis[i]){ 34 for(int j=i+1;j<=n;j++){ 35 if(!vis[j]){ 36 if(a[i]==b[j]&&(b[i]==a[j])){ 37 vis[i]=1,vis[j]=1; 38 cnt++; break; 39 } 40 } 41 } 42 } 43 } 44 int num=0; 45 for(int i=1;i<=n;i++) 46 if(!vis[i]) 47 num++; 48 cnt+=(num/3)*2; 49 cout<<cnt<<endl; 50 }
Sorting a Three-Valued Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。