线上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;
}