python/TangDou/XiTi/1270.cpp

#include <bits/stdc++.h>

using namespace std;

//n个人，r个水龙头
int n, r;
//打水时间
int t[101] = {0};
//第一维表示是几个水龙头，第二维表示现在这个水龙头排队的情况
int v1[101][101] = {0};

//https://blog.csdn.net/yutian74/article/details/89677889?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1.control
//找到哪一个队列是最先结束的队列,也就是当前来说最时间总和最短的
void getWhiceR(int &rInx, int &value, int &inx) { //三个返回值 rInx:第几个水龙头，value:现在总的时间有多长,inx:现在有几个人在排队
    value = INT32_MAX; //默认给了一个极大值，这样方便获取最小值
    //找到最少时间排队的队列
    for (int i = 1; i <= r; ++i) {
        int t = 0;
        int j;
        //当前水龙头的排队总时间
        for (j = 1; j <= 101; ++j) {
            if (v1[i][j] == 0) break;
            t += v1[i][j];
        }
        if (t < value) {
            value = t;
            rInx = i;       //记录是哪个水龙头
            inx = j - 1;    //记录是第几个位置
        }
    }
}

int main() {
    //输入+输出重定向
    freopen("../1270.txt", "r", stdin);
    //录入打水时间
    cin >> n >> r;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    //排序
    sort(t + 1, t + n + 1);//注意从数组索引1开始，则为t+1--->t+n+1

    //将每一个人员都模拟入入水龙头前
    for (int i = 1; i <= n; ++i) {
        //找出这r个队列中最先结束的那一个，放进去
        int rInx, value, inx;
        getWhiceR(rInx, value, inx);
        v1[rInx][inx + 1] = t[i];//将此人员放到探测出最适合放的水龙头队列中去排队
    }

    //输出结果,计算打水时间+等待时间
    int timeAll = 0;
    for (int i = 1; i <= r; ++i) {
        int j;
        for (j = 1; j <= 101; ++j) {
            if (v1[i][j] > 0) {
                cout << v1[i][j] << " ";
            } else {
                break;
            }
        }

        //回退一个
        j--;
        //计算等待时间+打水时间,j-1是停止的位置
        for (int k = 1; k <= j; k++) {
            timeAll += v1[i][k] * (j - k + 1); //前面的人员打水时间，都会累积成后面人员的等待时间，所以就是乘以 (length+1-k)*t的关系。
        }
        cout << endl;
    }

    cout << timeAll << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}