Bridge

分析：如果每次都让最快的人陪别人过桥，然后他再返回陪另一个人过桥，这是最佳方案吗？以sample输入为例：有4个人，过桥时间分别是：1 2 5 10。按前述策略的过桥方案为：

1 10

1

1 5

1

1 2

共19秒。但按照sample的过桥策略只要17秒：<!--more-->

1 2

1

5 10

2

1 2

该策略其实是：先让最快的2个人过桥，让最快的一个返回送手电，再让最慢的两个人过桥，让第二快的人返回送手电，最后2个人一起过桥。这是最佳方案吗？

如果把要过桥的人按照过桥时间从小到大排列得到数列：a1, a2, ..., a(n-1), a(n)。那么第二种策略可以表述为：

a1 a2

a1

a(n-1) a(n)

a2

经这4步，在最快的2个人的协助下，最慢的2个人过了桥，共用时：a1+2a2+a(n)秒；然后，最快的两个人接着再协助还没有过河的人中最慢的两个人过河；最后，最快的2个人一起过河，或者（在最后还剩3个人的情况下）：

a1 a3

a1

a1 a2

在第一种策略下，送最慢的2个人过河需要的时间：

a1 a(n-1)

a1

a1 a(n)

a1

经这4步，在最快的一个人的协助下，最慢的2个人过了桥，共用时：2a1+a(n-1)+a(n)秒。同样是送2个最慢的人过河，两种策略的时间差为：

delta = a1+2a2+a(n) - (2a1+a(n-1)+a(n)) = 2a2 - (a1 + a(n-1)) = (a2 - a1) - (a(n-1) - a2)

第二种策略只在delta小于0的情况下才优于第一种策略。另外我们注意到：如果有a(n-1)使得上面的delta不小于0,则对于a(n-2)直到a3，如果用这些值分别代替上式中的a(n-1)，delta都不小于0；也就是说，这这些情况下，第一种策略都不逊于第二种策略。

仔细思考，根据数列的情况，交替运用这2种策略，即可快速过河。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

inline int cross(vector<vector<int> > & order, int fast, int slow = 0) {
  if (!slow) {
    order.push_back(vector<int>(1, fast));
    return fast;
  }
  vector<int> group(2);
  group[0] = fast;
  group[1] = slow;
  order.push_back(group);
  return slow;
}

int min_time(vector<int> & people, vector<vector<int> > & order) {
  if (people.size() == 1) {
    order.push_back(vector<int>(1, people[0]));
    return people[0];
  }
  sort(people.begin(), people.end());
  int t = 0;
  int p0 = people[0];
  int p1 = people[1];
  while (!people.empty()) {
    int size = people.size();
    if (size == 2) {
      t += cross(order, p0, p1);
      people.clear();
    }
    else if (size == 3) {
      t += cross(order, p0, people[2]);
      t += cross(order, p0);
      t += cross(order, p0, p1);
      people.clear();
    }
    else {
      if (p1 - p0 < people[size - 2] - p1) {
        t += cross(order, p0, p1);
        t += cross(order, p0);
        t += cross(order, people[size - 2], people.back());
        t += cross(order, p1);
        people.pop_back();
        people.pop_back();
      }
      else {
        t += cross(order, p0, people.back());
        t += cross(order, p0);
        people.pop_back();
      }
    }
  }
  return t;
}

int main() {
  int n_case = 0;
  cin >> n_case;
  for (int i = 0; i < n_case; i++) {
    int n = 0;
    cin >> n;
    vector<int> people(n);
    int j;
    for (j = 0; j < n; j++)
      cin >> people[j];
    vector<vector<int> > order;
    int t = min_time(people, order);
    if (i != 0)
      cout << endl;
    cout << t << endl;
    for (j = 0; j < order.size(); j++) {
      for (int k = 0; k < order[j].size(); k++) {
        if (k != 0)
          cout << ' ';
        cout << order[j][k];
      }
      cout << endl;
    }
  }
}