接水问题的改编，做不出啦

题目描述
学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量不相等，第i个水龙头每秒钟的供水量记为Si。

现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j同学第x秒结束时完成接水，则k同学第x+1 秒立刻开始接水。 若当前接水人数n’不足m，则只有n’个龙头供水，其它m-n’个龙头关闭。

现在给出n名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。(
�
,
�
,
�
�
≤
1
0
6
m,n,Si≤10
6
)

输入
第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。

第2 行n个整数 w1、w2、、wn，每两个整数之间用一个空格隔开，wi表示 i 号同学的接水量。

第3行m个整数s1、s2、、 sn, 每两个整数之间用一个空格隔开，si表示i号水龙头每秒钟的供水量。

输出
输出只有一行，1个整数，表示接水所需的总时间。

样例
输入数据 1
5 3
4 4 1 2 1
1 2 3
输出数据 1
3

模拟过不了吗

乱码处理下
测试结果没达到预期

img

【以下回答由 GPT 生成】

解决方案：

首先，我们可以创建一个优先队列来维护当前正在接水的学生。

  1. 定义一个结构体表示学生，包括学生的编号和剩余接水量。
struct Student {
    int id;
    int water;

    Student(int _id, int _water) {
        id = _id;
        water = _water;
    }

    bool operator<(const Student& other) const {
        return water < other.water;
    }
};
  1. 读取输入的n和m，以及每个学生的接水量和每个水龙头的供水量。
int n, m;
cin >> n >> m;

vector<int> w(n);
for (int i = 0; i < n; i++) {
    cin >> w[i];
}

vector<int> s(m);
for (int i = 0; i < m; i++) {
    cin >> s[i];
}
  1. 创建一个优先队列pq，并将前m个学生加入队列。
priority_queue<Student> pq;

for (int i = 0; i < m; i++) {
    pq.push(Student(i, w[i]));
}
  1. 创建一个变量totalTime来记录接水总时间，并初始化为0。
int totalTime = 0;
  1. 进入一个循环，直到所有学生都接完水。
while (!pq.empty()) {
    // 取出当前接水量最少的学生
    Student curr = pq.top();
    pq.pop();

    // 更新接水总时间
    totalTime += curr.water;

    // 检查是否还有学生需要接水
    if (m < n) {
        // 取出下一个等待接水的学生
        int nextStudent = m;
        m++;

        // 更新该学生的接水量
        w[nextStudent] -= s[curr.id];

        // 检查该学生是否还需要接水
        if (w[nextStudent] > 0) {
            pq.push(Student(nextStudent, w[nextStudent]));
        }
    }
}
  1. 输出接水总时间。
cout << totalTime << endl;

完整代码如下：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Student {
    int id;
    int water;

    Student(int _id, int _water) {
        id = _id;
        water = _water;
    }

    bool operator<(const Student& other) const {
        return water < other.water;
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> w(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    vector<int> s(m);
    for (int i = 0; i < m; i++) {
        cin >> s[i];
    }

    priority_queue<Student> pq;

    for (int i = 0; i < m; i++) {
        pq.push(Student(i, w[i]));
    }

    int totalTime = 0;

    while (!pq.empty()) {
        Student curr = pq.top();
        pq.pop();

        totalTime += curr.water;

        if (m < n) {
            int nextStudent = m;
            m++;

            w[nextStudent] -= s[curr.id];

            if (w[nextStudent] > 0) {
                pq.push(Student(nextStudent, w[nextStudent]));
            }
        }
    }

    cout << totalTime << endl;

    return 0;
}

这样就能求解接水问题的总时间了。



【相关推荐】



如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^