Posted on 2007-06-11 22:00
ZelluX 阅读(396)
评论(0) 编辑 收藏 所属分类:
Algorithm
原来vim的复制快捷键是 " +y ，其中+也是要按的，怪不得以前一直不成功
/*
PROG: sort3
ID: 06301031
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ifstream fin("sort3.in");
ofstream fout("sort3.out");
int n;
fin >> n;
vector<int> nums(n);
int numCount[4];
numCount[1] = numCount[2] = numCount[3] = 0;
for (int i = 0; i < n; i++)
{
fin >> nums[i];
numCount[nums[i]]++;
}
numCount[2] += numCount[1];
numCount[3] += numCount[2];
int toBeChanged[4][4];
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
toBeChanged[i][j] = 0;
for (int i = 0; i < n; i++)
{
int sortedNum = 1;
for (int j = 1; j < 4; j++)
if (i - numCount[j] < 0)
{
sortedNum = j;
break;
}
cout << nums[i] << ":" << sortedNum << endl;
if (nums[i] != sortedNum)
toBeChanged[nums[i]][sortedNum]++;
}
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
if (toBeChanged[i][j] != 0)
cout << i << "," << j << ":" << toBeChanged[i][j] << endl;
int triangles = 0;
int swaps = 0;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
if (toBeChanged[i][j] != 0)
{
int smaller = toBeChanged[i][j];
if (toBeChanged[j][i] < smaller)
smaller = toBeChanged[j][i];
toBeChanged[i][j] -= smaller;
toBeChanged[j][i] -= smaller;
swaps += smaller;
}
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
if (toBeChanged[i][j] != 0)
triangles += toBeChanged[i][j];
cout << swaps << endl << triangles << endl;
swaps += (triangles / 3 * 2);
fout << swaps << endl;
return 0;
}