一本通-1319：【例6.1】排队接水（贪心）

【题目描述】

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

【输入】

共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

【输出】

有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

【输入样例】

10                          
56 12 1 99 1000 234 33 55 99 812

【输出样例】

3 2 7 8 1 4 9 6 10 5
291.90

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 0x0ffffff;

struct Node
{
    int number, value;
    bool operator<(const Node & obj) const
    {
        return value < obj.value;
    }
};

int n = 1005;
vector<Node> sequence(n);

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> sequence[i].value;
        sequence[i].number = i;
    }
    sort(sequence.begin() + 1, sequence.begin() + 1 + n);

    int sum = 0;
    for (int i = 1; i <= n - 1; ++i) {
        cout << sequence[i].number << " ";
        sum += (n - i) * sequence[i].value;
    }
    cout << sequence[n].number << endl;
    cout << fixed << setprecision(2) << (sum * 1.0) / n << endl;

    return 0;
}

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

struct Node
{
    long long waterTime;
    int number;

    bool operator<(const Node & obj) const
    {
        return waterTime < obj.waterTime;
    }
};

int n;
vector<Node> seq(1005);

void solve()
{
    sort(seq.begin(), seq.begin() + n);

    long long totalWait = 0, personalWait = 0;

    cout << seq[0].number << ' ';
    for (int i = 1; i < n; ++i) {
        cout << seq[i].number;
        if (i != n - 1) cout << ' ';

        personalWait += seq[i - 1].waterTime;
        totalWait += personalWait;
    }
    cout << endl;

    cout << fixed << setprecision(2) << (totalWait * 1.0) / n << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i].waterTime;
        seq[i].number = i + 1;
    }

    solve();

    return 0;
}