首页 > 代码库 > USACO Section 2.1: Sorting a Three-Valued Sequence
USACO Section 2.1: Sorting a Three-Valued Sequence
简单题
1 /* 2 ID: leetcod3 3 PROG: sort3 4 LANG: C++ 5 */ 6 #include <iostream> 7 #include <fstream> 8 #include <string> 9 #include <map> 10 #include <vector> 11 #include <set> 12 #include <algorithm> 13 #include <queue> 14 #include <cmath> 15 #include <list> 16 #include <cstring> 17 #include <cstdlib> 18 #include <limits> 19 #include <stack> 20 21 using namespace std; 22 23 ofstream fout ("sort3.out"); 24 ifstream fin ("sort3.in"); 25 26 int N; 27 28 int main() 29 { 30 fin >> N; 31 vector<int> input(N); 32 int one, two, three; 33 one = two = three = 0; 34 for (int i = 0; i < N; ++i) { 35 fin >> input[i]; 36 if (input[i] == 1) one++; 37 else if (input[i] == 2) two++; 38 else three++; 39 } 40 int pos[4][4] = {0}; 41 for (int i = 0; i < one; ++i) pos[1][input[i]]++; 42 for (int i = one; i < one+two; ++i) pos[2][input[i]]++; 43 for (int i = one+two; i < N; ++i) pos[3][input[i]]++; 44 for (int i = 1; i < 4; ++i) { 45 //for (int j = 1; j < 4; ++j) cout << pos[i][j] << " "; 46 //cout << endl; 47 } 48 int ans = 0; 49 for (int i = 1; i <= 3; ++i) { 50 for (int j = i; j <= 3; ++j) { 51 if (i == j) continue; 52 int tmp = min(pos[i][j], pos[j][i]); 53 ans += tmp; 54 pos[i][j] -= tmp; 55 pos[j][i] -= tmp; 56 } 57 } 58 int tmp = 0; 59 //cout << ans << endl; 60 for (int i = 1; i <= 3; ++i) { 61 for (int j = 1; j <= 3; ++j) { 62 if (i == j) continue; 63 tmp += pos[i][j]; 64 } 65 } 66 //cout << tmp << endl; 67 ans += tmp / 3 * 2; 68 fout << ans << endl; 69 70 return 0; 71 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。