石油大学OJ组队赛11 C 三元排序-白红宇

石油大学OJ组队赛11 C 三元排序

阅读量：4312 次

发布时间：2019-06-06

本文共 2024 字，大约阅读时间需要 6 分钟。

问题 C: 三元排序

时间限制: 1 Sec

内存限制: 128 MB

提交: 101

解决: 23

[ ][ ][ ]

题目描述

一次交换操作是指将数列中的两个数位置对调。给出一个只有1、2、3三个元素的数列，你需要通过有限次交换使数列中的数从小到大排列。请求出最少需要的交换次数。

输入

第一行读入一个数N（N<=100000），它代表数列的长度。

以下N行每行一个数。每个数都只可能是1、2、3中的一个。

输出

将最少的交换次数输出

样例输入

样例输出

提示

最少交换次数，上一次的数据是1000 这一次是10w

数据会超时，

原理一样，统计1,2,3，的数目，扫描1，去2 里扫，2没有去3，同理2

增加限制条件以防TLE

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
           #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #define mem(a,b) memset(a,b,sizeof(a))#define findx(x) lower_bound(b+1,b+1+bn,x)-b#define FIN freopen("input.txt","r",stdin)#define FOUT freopen("output.txt","w",stdout)#define S1(n) scanf("%d",&n)#define SL1(n) scanf("%I64d",&n)#define S2(n,m) scanf("%d%d",&n,&m)#define SL2(n,m) scanf("%I64d%I64d",&n,&m)#define Pr(n) printf("%d\n",n) using namespace std;typedef long long ll; const double PI=acos(-1);const int INF=0x3f3f3f3f;const double esp=1e-6;const int maxn=1e5+5;const int MOD=1e9+7;const int mod=1e9+7;int dir[5][2]={0,1,0,-1,1,0,-1,0}; int a[maxn];int main(){ int n,c,k1,k2,k3; while (cin>>n) { ll ans=0; k1=k2=k3=0; memset(a,0,sizeof(a)); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); if (a[i]==1) k1++; if (a[i]==2) k2++; } int m1=k1; int m2=k2; int m3=k1+k2; int m4=m3; c=k1+k2; for (int i=1;i<=n;i++) { if (i>=m4+1) break; if (i>m1&&i<=m4) { if (a[i]!=2) { for (int j=c+1;j<=n;j++) { if (a[j]==2) { swap(a[j],a[i]); c=j; ans++; break; } } } } else if (i<=m1) { if (a[i]==2) { int j; for (j=k1+1;j<=m4;j++) { if (a[j]==1) { swap(a[i],a[j]); k1=j; ans++; break; } } if (j>m4) { for (j=m3+1;j<=n;j++) { if (a[j]==1) { swap(a[i],a[j]); m3=j; ans++; break; } } } } else if (a[i]==3) { int j; for (j=m3+1;j<=n;j++) { if (a[j]==1) { swap(a[i],a[j]); m3=j; ans++; break; } } if (j>n) { for (j=k1+1;j<=m4;j++) { if (a[j]==1) { swap(a[i],a[j]); k1=j; ans++; break; } } } } } } cout<
                   
                    <