#include<stdio.h> #include<memory.h> #include<algorithm> #include<queue> using namespace std; #define N 1020 queue < pair< int, int> > ans2; int main(void) { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); int t, n, tempn, p, ans = 0; int man[N]; scanf("%d", &t); for(int i = 0; i<t; i++){ scanf("%d", &n); memset(man, 0, sizeof(int) * N); ans = 0; for(int j = 0; j<n; j++){ scanf("%d", &man[j]); } sort(man, man + n); tempn = n; p = n-1; while(tempn > 0){ if(tempn >= 4){ if(man[0] + man[1] + man[p] + man[1] > man[p] + man[0] + man[p-1] + man[0]){ ans += man[p] + man[0] + man[p-1] + man[0]; ans2.push(make_pair(man[0], man[p])); ans2.push(make_pair(man[0], -1)); ans2.push(make_pair(man[0], man[p-1])); ans2.push(make_pair(man[0], -1)); } else{ ans += man[0] + man[1] + man[p] + man[1]; ans2.push(make_pair(man[0], man[1])); ans2.push(make_pair(man[0], -1)); ans2.push(make_pair(man[p-1], man[p])); ans2.push(make_pair(man[1], -1)); } tempn -= 2; p -= 2; } else{ if(tempn == 3){ ans += man[0] + man[p] + man[1]; ans2.push(make_pair(man[0], man[p])); ans2.push(make_pair(man[0], -1)); ans2.push(make_pair(man[0], man[1])); tempn = 0; } else if(tempn == 2){ ans += man[1]; ans2.push(make_pair(man[0], man[1])); tempn = 0; } else if(tempn == 1){ ans += man[0]; ans2.push(make_pair(man[0], -1)); tempn = 0; } } } printf("%d\n", ans); while(!ans2.empty()){ pair <int, int> temp; temp = ans2.front(); ans2.pop(); printf("%d", temp.first); if(temp.second != -1)printf(" %d", temp.second); printf("\n"); } if(i != t-1)printf("\n"); } }
10545698 10037 Bridge Accepted C++ 0.012 2012-08-31 04:45:34