♐ CSP_J 组真题
2010年
2. 接水问题

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1950 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/444/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P1190 (opens in a new tab)

解法一、朴素模拟

核心思想:

朴素模拟:
1、先给每个b[i]水龙头分配一个人a[i],b[i]表示水龙头的剩余时间。同时标记该水龙头为 used 使用中
2、每一次 while 循环表示1秒,即接水时间+1。同时每个水龙头的剩余时间 b[i]--
3、如果某个水龙头的剩余时间 b[i] 减到了0,则把队列中的 a[j] 分配给b[i]。同时 j++ 指向下一个人
4、如果某个水龙头的剩余时间 b[i] 减到了0,但是队伍中已经没有排队等待接水的人了(j>n),则设置used[i] = 0 表示关闭 b[i] 水龙头,同时关闭的数量 cnt++
5、当关闭水龙头的数量 cnt==n 时,说明所有水龙头都已经关闭,此时的接水时间 t 就是最终结果

题解代码:
解法一、朴素模拟
#include <bits/stdc++.h>
using namespace std;
 
const int M = 105, N = 10005;
int a[N], b[M], used[M]={0};
int n, m;
 
/*
朴素模拟:
1、先给每个b[i]水龙头分配一个人a[i],b[i]表示水龙头的剩余时间。同时标记该水龙头为 used 使用中
2、每一次 while 循环表示1秒,即接水时间+1。同时每个b[i]--。
3、如果b[i]减到了0,则把队列中的 a[j]分配给b[i]。同时 j++ 指向下一个人
4、如果b[i]减到了0,但是队伍中已经没有排队等待接水的人了(j>n),则设置used[i] = 0 表示关闭 b[i] 水龙头,同时关闭的数量 cnt++
5、当关闭水龙头的数量 cnt==n 时,说明所有水龙头都已经关闭,此时的接水时间 t 就是最终结果
*/
int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)  scanf("%d", &a[i]);
 
    for(int i = 1; i <= m; i++)
    {
        b[i] = a[i];  // 初始分配水龙头
        used[i] = 1;  // 该水龙头标记为使用中
    }
 
    int t = 0, cnt = 0;  // t表示总接水时间,cnt表示关闭的水龙头数量
    int j = m + 1;  // 由于前m个水龙头都已经初始分配了,故第一个等待排队的是 m+1
    while(cnt < m)  // 跳出条件:水龙头全部关闭
    {
        t++;  // 总接水时间++
        for(int i = 1; i <= m; i++)   // 循环m个水龙头
        {
            if(used[i])  // 如果当前水龙头在使用中
            {
                b[i]--;  // 则b[i]--
                if(b[i] == 0)  // 如果 b[i] 减到0
                {
                    if(j<= n)  b[i] = a[j++]; // 如果还有人在排队,则第一个排队的人接到b[i]
                    else  // 如果没人在排队
                    {
                        used[i] = 0; // 则关闭该水龙头
                        cnt++; // 关闭数量++
                    }
                }
            }
        }
    }
 
    printf("%d\n", t);
    return 0;
}