SGU 138 Games of Chess構造


タイトルリンクはこちら
簡単にyyが構造的に出てきます
試合回数は明らかにsum/2(sumは1人当たり出荷回数の和)
まず出場回数順に並べて、大きいから小さいまで順番に埋めます.
構造は
winner a a a a a a b b b b b c c c ……
loser                  b             c      d
このような形をして、敗者が空いているところを埋めて、winnerとloserが同じ人ではないことを証明しやすい.
コードは次のとおりです.
#include <bits/stdc++.h>

#define up(i, lower, upper) for(int i = lower; i < upper; i++)
#define down(i, lower, upper) for(int i = upper-1; i >= lower; i--)

using namespace std;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef long long ll;
typedef unsigned long long ull;

const double pi = acos(-1.0);
const double eps = 1.0e-9;

template<class T>

inline bool read(T &n){
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}

template <class T>
inline void write(T n) {
    if(n < 0) {
        putchar('-');
        n = -n;
    }
    int len = 0,data[20];
    while(n) {
        data[len++] = n%10;
        n /= 10;
    }
    if(!len) data[len++] = 0;
    while(len--) putchar(data[len]+48);
}

///---------------------------------------------------------

struct node {
    int num, cnt;
    node() :cnt(0) {}
    friend bool operator < (node a, node b){
        return a. cnt > b. cnt;
    }
};

node a[101];
int winner[10001], loser[10001];

int main() {
    int n;
    read(n);
    up(i, 1, n+1) a[i].num = i;
    int sum = 0;
    up(i, 1, n+1) {
        read(a[i].cnt);
        sum += a[i].cnt;
    }
    sort(a+1, a+n+1);
    sum /= 2;
    int pt = 1;
    up(i, 0, sum) {
        if(a[pt].cnt>1) winner[i] = a[pt].num, a[pt].cnt--;
        else {
            loser[i] = a[pt].num, a[pt].cnt--;
            while(a[pt].cnt <= 1) pt++;
            winner[i] = a[pt].num, a[pt].cnt--;
        }
    }
    pt = 1;
    up(i, 0, sum) {
        if(!loser[i]) {
           while(a[pt].cnt < 1) pt++;
           loser[i] = a[pt].num, a[pt].cnt--;
        }
    }
    write(sum); puts("");
    up(i, 0, sum) printf("%d %d
", winner[i], loser[i]); }