USER: tianbing tianbing [tbbd4261]
TASK: sort3
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 2932 KB]
Test 2: TEST OK [0.000 secs, 2932 KB]
Test 3: TEST OK [0.022 secs, 2932 KB]
Test 4: TEST OK [0.000 secs, 2932 KB]
Test 5: TEST OK [0.011 secs, 2932 KB]
Test 6: TEST OK [0.022 secs, 2932 KB]
Test 7: TEST OK [0.000 secs, 2932 KB]
Test 8: TEST OK [0.000 secs, 2932 KB]
All tests OK.
Your program ('sort3') produced all correct answers! This is your
submission #5 for this problem. Congratulations!
用cnt[i]紀錄i的數目，數目確定了i應該在的范圍也就確定了
用s[i][j]表示應該出現i的范圍內中含有j的數目
1 如果i中有j，j中有i，直接交換即可，交換一次
2 第一種情況交換完以后，如果 1中有2 ，2中有3，則3中必然有1 這種情況需交換2次才能排好序
或者反過來，2中有1，3中有2, 1中有3，同樣交換兩次
/*
ID:tbbd4261
PROG:sort3
LANG:C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("sort3.in");
ofstream fout("sort3.out");
int arr[1005]={0};
int cnt[4]={0};
int s[4][4]={0};
int min(int a,int b)
{
return a>b?b:a;
}
int main()
{
int n,i,j;
fin>>n;
for(i=1; i<=n; i++)
{
fin>>arr[i];
cnt[arr[i]]++;
}
for(i=1; i<=cnt[1]; i++)
s[1][arr[i]]++;
for(i=cnt[1]+1; i<=cnt[1]+cnt[2]; i++)
s[2][arr[i]]++;
for(i=cnt[1]+cnt[2]+1; i<=n; i++)
s[3][arr[i]]++;
int ans=0;
for(i=1; i<=3; i++)
for(j=1; j<=3; j++)
{
if(i==j)continue;
int temp=min(s[i][j],s[j][i]);
ans+=temp;
s[i][j]-=temp; s[j][i]-=temp;
}
ans+=min(s[1][2],min(s[2][3],s[3][1]))*2;
ans+=min(s[3][2],min(s[2][1],s[1][3]))*2;
fout<<ans<<endl;
//system("pause");
return 0;
}