Games of Chess

题目描述

$N$ friends gathered in order to play chess, according to the following rules. In the first game, two of the $N$ friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the $N$ friends played, find a schedule for the games, so that the above rules are obeyed.

题意概述

有$N$个人玩游戏，第一局任意两个人参加，第一局胜利者和除他以外的一个人参加第二局（可以选择第一局失败者），第二局胜利者和除他以外的一个人参加第三局…不存在平局。给定每个人参加游戏的局数，构造一种可行的游戏方案。

数据范围：$2 \le N \le 100$。

算法分析

显然每个人参加游戏的次数之和为偶数，除以$2$即是游戏局数。考虑安排每一局的胜利者和失败者。设某个人参加游戏的次数为$n$，则先安排他连续胜利$(n-1)$局，接着失败一局，直到安排了所有局的胜利者。在安排失败者的时候，要注意不能和胜利者相同，因此应尽量先安排参加游戏局数较多的人胜利，减少冲突的可能。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 110;
  int n, sum;
  pair <int, int> a[N];
  vector <pair <int, int> > ans;
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > a[i].first, a[i].second = i, sum += a[i].first;
  }
  void process() {
    io < sum >> 1 < '\n';
    sort(a + 1, a + n + 1, greater <pair <int, int> >());
    int p = 1;
    for (int i = 0; i < sum >> 1; ++ i) {
      if (a[p].first == 1) ans.push_back(make_pair(a[p + 1].second, a[p].second)), -- a[p].first, -- a[++ p].first;
      else ans.push_back(make_pair(a[p].second, 0)), -- a[p].first;
    }
    for (int i = 0; i < sum >> 1; ++ i)
      if (! ans[i].second)
        for (int j = 1; j <= n; ++ j) if (a[j].first && a[j].second != ans[i].first) { ans[i].second = a[j].second, -- a[j].first; break; }
    for (int i = 0; i < sum >> 1; ++ i) io < ans[i].first < ' ' < ans[i].second < '\n';
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}