【CODEFORCES】Pupils Redistribution
CODEFORCEの問題を解きました.
http://codeforces.com/contest/779/problem/A
難しさ(初心者目線)
・考え方**
・実装*
・面白さ*
問題
幸多高校には2つのクラス(A,B)があります.
クラスの人数は共にn人です.
クラス対抗プログラミングコンテストを行ったところ、
クラスAとクラスBのそれぞれの人の成績がa_1,a_2,…,a_n,b_1,b_2,…,b_nとなりました.
成績は1,2,3,4,5点でつけられます.
片方のクラスが極端に強くなってしまってはつまらないので、
それぞれのクラスの人の成績の和が等しくなるように生徒を交換したいです.
交換は1人対1人で行います.
それぞれのクラスの生徒の成績が与えられるので、
最小で何回の交換を行うことで、クラスAとクラスBの生徒の成績の和を等しくできるか求めてください.
制約
1≦n≦100(整数)
1≦a_i,b_i≦5(整数)
入力
n
a_1 a_2 … a_n
b_1 b_2 … b_n
出力
最小値を出力
等しくできない場合は-1を出力
方針
・それぞれの成績の人の人数が偶数でないといけない
・それぞれの成績の人の人数が偶数の場合O(n)で解くことができる
コード
WhyamIhereさんのコード参考にしました.
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> using namespace std; #define pb push_back #define mp make_pair #define ll long long #define PI acos(-1.0) #define ALL(A) ((A).begin(), (A).end()) #define vsort(v) sort(v.begin(),v.end()) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) int main(){ int n; cin >> n; //a[i]:クラスAの成績iが何人いるか //total[i]:クラスA,Bで成績iが何人いるか int a[6] = {0}, b[6] = {0}, total[6] = {0}; FOR(i, 0, n){ int input; cin >> input; a[input]++;total[input]++; } FOR(i, 0, n){ int input; cin >> input; b[input]++;total[input]++; } //それぞれの成績の人が偶数でないと二つのクラスに分けられない FOR(i, 1, 6){ if(total[i]%2==1){ cout << -1 << endl; return 0; } } //分けられる場合 //目指す値との差が2*xならx回交換すれば良い int ans = 0; FOR(i, 1, 6){ ans += abs(total[i] / 2 - a[i]); } ans /= 2; cout << ans << endl; }