2012年8月30日

UVa 10037 - Bridge

Reference : http://www.csie.ntnu.edu.tw/~u91029/Greedy.html#4
#include <cstdio>
#include <algorithm>

int main() {
  int i, n, c, num[1001];
  scanf("%d", &c);
  while (c--) {
    scanf("%d", &n);
    for (i = 0; i < n; i++)
      scanf("%d", &num[i]);
    std::sort(num, num + n);
    int t = 0, t1, t2, rec = n;
    
    for (n--; n >= 3; n -= 2) {
      t1 = num[0] + num[1] * 2 + num[n];
      t2 = num[0] * 2 + num[n - 1] + num[n];
      if (t1 < t2) t += t1;
      else t += t2;
    }

    if (n == 2) t += num[0] + num[1] + num[2];
    else if (n == 1) t += num[1];
    else t += num[0];
    printf("%d\n", t);

    n = rec;

    for (n--; n >= 3; n -= 2) {
      t1 = num[0] + num[1] * 2 + num[n];
      t2 = num[0] * 2 + num[n - 1] + num[n];
      if (t1 < t2) printf("%d %d\n%d\n%d %d\n%d\n", num[0], num[1], num[0], num[n - 1], num[n], num[1]);
      else printf("%d %d\n%d\n%d %d\n%d\n", num[0], num[n], num[0], num[0], num[n - 1], num[0]);
    }

    if (n == 2) printf("%d %d\n%d\n%d %d\n", num[0], num[1], num[0], num[0], num[2]);
    else if (n == 1) printf("%d %d\n", num[0], num[1]);
    else printf("%d\n", num[0]);
    if (c) puts("");
  }
  return 0;
}

沒有留言:

張貼留言