読者です 読者をやめる 読者になる 読者になる

プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【CODEFORCES】Pupils Redistribution

CODEFORCES 競技プログラミング

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;
}