usaco_sort3.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:sort3
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin ("sort3.in");
ofstream fout ("sort3.out");   

int main()
{
    int a[1001];
    int nn[4]={0,0,0,0};
    int n13=0,n23=0,n12=0,n31=0,n32=0,n21=0;
    int i,sum=0,n;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
        nn[a[i]]++;
    }
    for(i=1;i<=nn[1];i++)
    {
        if(a[i]==2) n12++;
        if(a[i]==3) n13++;
    }
    for(i=nn[1]+1;i<=nn[1]+nn[2];i++)
    {
        if(a[i]== 1) n21++;
        if(a[i]== 3) n23++;
    }
    for(i=nn[1]+nn[2]+1;i<=n;i++)
    {
        if(a[i]== 1) n31++;
        if(a[i]== 2) n32++;
    }
    int t;
    if(fabs(n12-n21)) {t=n12>n21?n21:n12;  n21-=t;n12-=t;sum+=t;}
    else{t=n12;n12=0;n21=0;sum+=t;}
    if(fabs(n13-n31)) {t=n13>n31?n31:n13;  n31-=t;n13-=t;sum+=t;}
    else{t=n13;n13=0;n31=0;sum+=t;}
    if(fabs(n32-n23)) {t=n32>n23?n23:n32;  n23-=t;n32-=t;sum+=t;}
    else{t=n32;n32=0;n23=0;sum+=t;}
    sum+=(n12+n21+n13+n31+n23+n32)*2/3;
    fout<<sum<<endl;
   // system("PAUSE");
    return 0;
}