ACM UVA 10037 (Problem D: Bridge)

题目：

思路：

Greedy。

当人数小于4时，很简单。
当人数大于等于4时，有两种策略可以选择。我们设当前有A,B,...Y,Z没有过桥。我们可以有以下两个策略：
1. AB + A + YZ + B
2. AZ + A + AY + A
然后选择这两个策略中耗时最小的一个。

代码：

/*
 *******************************************************************************
 *
 * Filename: 10037.cpp
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

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

using namespace std;


int main()
{
    int caseNum = 0;
    int peopleNum = 0;
    int peopleTime[1000];
    int timeResult = 0;
    vector<string> result;
    char buffer[120];

    cin >> caseNum;
    for (; caseNum != 0; caseNum--) {
        result.clear();
        timeResult = 0;
        cin >> peopleNum;
        for (int i = 0; i < peopleNum; i++) {
            cin >> peopleTime[i];
        }
        while (peopleNum > 3) {
            int time1 = peopleTime[1] + peopleTime[0] + peopleTime[peopleNum-1] + peopleTime[1];
            int time2 = peopleTime[peopleNum-1] + peopleTime[0] + peopleTime[peopleNum-2] + peopleTime[0];
            if (time1 < time2) {
                sprintf(buffer, "%d %d\n%d\n%d %d\n%d\n",
                        peopleTime[0], peopleTime[1], peopleTime[0],
                        peopleTime[peopleNum-2], peopleTime[peopleNum-1],
                        peopleTime[1]);
                timeResult += time1;
            } else {
                sprintf(buffer, "%d %d\n%d\n%d %d\n%d\n",
                        peopleTime[0], peopleTime[peopleNum-1],
                        peopleTime[0], peopleTime[0], peopleTime[peopleNum-2],
                        peopleTime[0]);
                timeResult += time2;
            }
            result.push_back(string(buffer));
            peopleNum -= 2;
        }

        if (peopleNum == 2) {
            sprintf(buffer, "%d %d\n", peopleTime[0], peopleTime[1]);
            timeResult += peopleTime[1];
        } else if (peopleNum == 3) {
            sprintf(buffer, "%d %d\n%d\n%d %d\n", peopleTime[0], peopleTime[1],
                    peopleTime[0], peopleTime[0], peopleTime[2]);
            timeResult += peopleTime[0] + peopleTime[1] + peopleTime[2];
        } else if (peopleNum == 1) {
            sprintf(buffer, "%d\n", peopleTime[0]);
            timeResult += peopleTime[0];
        }

        result.push_back(string(buffer));
        cout << timeResult << endl;
        for (int i = 0; i < result.size(); i++) {
            cout << result[i];
        }
        
        if (caseNum != 1) {
            cout << endl;
        }
    }
}