sgu400.cpp

SGU题库第四版前10题的题目解答。前三题是CPP程序

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxl = 2000;
const int maxn = 200;
const int maxp = 30;
const int maxlen = 1000000;
const int cost = 241;
const int inf = 0x7fffffff;

char str[maxlen];

struct Team {
  char name[maxl];
  bool solved[maxp];
  int reject[maxp];
  int num, penalty;
};

Team team[maxn], _team[maxn];
bool used[maxn];
int pp, n, left, _left, care;

int Next_Int(const char *str) {
  int m = 0, i;
  for (i = 0; isdigit(str[i]); i++)
    m = m * 10 + str[i] - '0';
  return m;
}

void Skip_Back(int &i) {
  for (; !isdigit(str[i]); i--);
  for (; isdigit(str[i]); i--);
}

void Skip_Forward(int &i) {
  for (; !isdigit(str[i]); i++);
  for (; isdigit(str[i]); i++);
}

void Init() {
  int i, j, k;
  for (i = 0; str[i] != '='; i++);
  for (; str[i] != 'y'; i++);
  for (pp = 0; str[i]; i++)
    pp += isupper(str[i]);
  n = 0;
  while (1) {
    gets(str);
    //printf("str = %s\n", str);
    for (i = 0; !isdigit(str[i]); i++);
    for (j = strlen(str) - 1; !isdigit(str[j]); j--);
    for (k = i; k <= j && isdigit(str[k]); k++);
    if (k > j) break;
    for (i = 0; i < pp; i++) {
      team[n].solved[i] = 0;
      team[n].reject[i] = 0;
    }
    team[n].num = 0;
    for (i = j = 0; str[i]; i++)
      switch (str[i]) {
      case '.' : j++; break;
      case '+' : team[n].solved[j++] = 1; team[n].num++; break;
      case '-' : team[n].reject[j++] = Next_Int(str + i + 1); break;
      }
    for (i = 0; !strchr(".+-", str[i]); i++);
    Skip_Back(i);
    team[n].penalty = Next_Int(str + i + 1);
    Skip_Back(i);
    for (; str[i] <= ' '; i--);
    str[i + 1] = 0;
    for (i = 0, Skip_Forward(i); str[i] <= ' '; i++);
    strcpy(team[n].name, str + i);
    n++;
  }
  sscanf(str, "%d", &left);
  gets(str);
  for (i = strlen(str) - 1; str[i] <= ' '; i--);
  str[i + 1] = 0;
  for (i = 0; str[i] <= ' '; i++);
  for (j = 0; j < n; j++)
    if (!strcmp(str + i, team[j].name)) {
      care = j;
      break;
    }
/*
  for (i = 0; i < n; i++) {
    printf("name = %s\n", team[i].name);
    printf("num = %d\n", team[i].num);
    printf("penalty = %d\n", team[i].penalty);
    for (j = 0; j < pp; j++)
      printf(" %d ", team[i].solved[j]);
    printf("\n");
    for (j = 0; j < pp; j++)
      printf(" %d ", team[i].reject[j]);
    printf("\n==\n");
  }
*/
}

void Best() {
  _left = left;
  int i, j, mm;
  for (i = 0; i < n; i++)
    _team[i] = team[i];
  while (left && team[care].num < pp) {
    mm = inf;
    for (i = 0; i < pp; i++)
      if (!team[care].solved[i] && team[care].reject[i] < mm) {
        j = i;
        mm = team[care].reject[i];
      }
    team[care].penalty += 20 * mm + cost;
    team[care].num++;
    team[care].solved[j] = 1;
    left--;
  }
  int rival = 0, add;
  for (i = 0; i < n; i++)
    used[i] = 0;
  for (i = 0; i < n; i++)
    if (i != care && (team[i].num > team[care].num || team[i].num == team[care].num && team[i].penalty < team[care].penalty)) {
      rival++;
      used[i] = 1;
      left -= min(left, pp - team[i].num);
    }
  for (i = 0; i < n; i++)
    if (i != care && team[i].num < team[care].num) {
      add = min(left, team[care].num - team[i].num);
      if (add) {
        team[i].num += add;
        team[i].penalty = inf;
      }
      left -= add;
    }
  for (i = 0; left && i < n; i++)
    if (i != care && !used[i]) {
      add = min(left, pp - team[i].num);
      rival++;
      left -= add;
    }
  printf("%d ", rival + 1);
}

void Worst() {
  left = _left;
  int i, j, k, mm, mm2, rival = 0, ll, ii;
  for (i = 0; i < n; i++)
    team[i] = _team[i];
  for (i = 0; i < n; i++)
    used[i] = 0;
  for (i = 0; i < n; i++)
    if (i != care && (team[i].num > team[care].num || team[i].num == team[care].num && team[i].penalty < team[care].penalty)) {
      used[i] = 1;
      rival++;
    }
  Team curr;
  while (left) {
    mm = inf;
    for (i = 0; i < n; i++)
      if (i != care && !used[i]) {
        curr = team[i];
        ll = left;
        while (curr.num < team[care].num || curr.num == team[care].num && curr.penalty >= team[care].penalty) {
          if (curr.num == pp || !ll) break;
          mm2 = inf;
          for (j = 0; j < pp; j++)
            if (!curr.solved[j] && curr.reject[j] < mm2) {
              mm2 = curr.reject[j];
              k = j;
            }
          curr.solved[k] = 1;
          curr.num++;
          curr.penalty += mm2 * 20 + cost;
          ll--;
        }
        if (curr.num < team[care].num || curr.num == team[care].num && curr.penalty >= team[care].penalty) continue;
        if (left - ll < mm) {
          mm = left - ll;
          ii = i;
        }
      }
    if (mm == inf) break;
    used[ii] = 1;
    rival++;
    left -= mm;
    team[ii].num += mm;
  }
  printf("%d\n", rival + 1);
}

void Work() {
  Best();
  Worst();
}

int main() {
  while (gets(str)) {
    Init();
    Work();
  }
  return 0;
}