视频加载失败

人满为患

864 字
4 分钟
人满为患

奶茶店取餐#

题目描述#

一家奶茶店共有 nn 位顾客,编号为 1,2,…,n1,2,\ldots,n,每位顾客点一杯奶茶。各位顾客的点单时刻、到店时刻、奶茶制作时间用数组 a1,a2,…,ana_1,a_2,\ldots,a_n、b1,b2,…,bnb_1,b_2,\ldots,b_n、c1,c2,…,cnc_1,c_2,\ldots,c_n 表示,其中 ai,bi,cia_i,b_i,c_i 表示第 ii 位顾客的点单时刻、到店时刻、奶茶制作时间。保证所有顾客的点单时刻互不相同。

系统按照点单时刻从小到大的顺序,为顾客依次分配 1,2,…,n1,2,\ldots,n 的取餐号。

奶茶店严格按照取餐号从小到大的顺序制作奶茶,同一时刻只能制作一杯。每杯奶茶在顾客点单且所有取餐号更小的奶茶均制作完成后立即开始制作,制作完成后立即放入出餐口。

店内有 1010 个出餐口,编号为 00 至 99。取餐号为 jj 的奶茶放入编号为 j mod 10j\bmod 10 的出餐口,各出餐口中的奶茶按取餐号从小到大的顺序排成队列。顾客到店后,一旦自己的奶茶已制作完成,且排在对应出餐口的最前方,就会立即将其取走。

请你计算每位顾客的等待时间,即取餐时刻与到店时刻之差。

输入描述#

每个测试文件均包含多组测试数据。第一行输入一个整数 TT(1≤T≤1041\le T\le 10^4)代表数据组数,每组测试数据描述如下:

第一行输入一个整数 nn(1≤n≤2×1051\le n\le 2\times 10^5)代表顾客数量。

此后 nn 行,第 ii 行输入三个整数 ai,bi,cia_i,b_i,c_i(1≤ai,bi,ci≤1091\le a_i,b_i,c_i\le 10^9;ai≤bia_i\le b_i),代表第 ii 位顾客的点单时刻、到店时刻、奶茶制作时间。保证所有 aia_i 互不相同。

除此之外,保证单个测试文件的 nn 之和不超过 2×1052\times 10^5。

输出描述#

对于每组测试数据,新起一行。

输出 nn 个整数,第 ii 个整数表示第 ii 位顾客的等待时间。

示例 1#

输入#

2
3
10 15 5
5 10 10
12 13 5
12
1 100 1
2 100 1
3 3 1
4 4 1
5 5 1
6 6 1
7 7 1
8 8 1
9 9 1
10 10 1
11 11 1
12 12 1

输出#

5 5 12
0 0 1 1 1 1 1 1 1 1 89 88

说明#

第二组样例的过程如下:

  • t=2t=2 时,1 号奶茶制作完成;t=3t=3 时,2 号奶茶制作完成,但这两位顾客都要到 t=100t=100 才到店。
  • 3~10 号顾客均在各自到店后的下一时刻取到奶茶,等待时间都是 11。
  • t=12t=12 时,11 号奶茶制作完成,但在出餐口 1 排在 1 号奶茶后面,无法取走。
  • t=13t=13 时,12 号奶茶制作完成,但在出餐口 2 排在 2 号奶茶后面,无法取走。
  • t=100t=100 时,1、2 号顾客到店并立即取走奶茶,等待时间均为 00。随后 11、12 号顾客也立即取走奶茶,等待时间分别为 100−11=89100-11=89 和 100−12=88100-12=88。

我的代码#

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct p
{
ll a;
ll b;
ll c;
ll d; //制作结束时间
ll e;
ll an;
ll id;
};
int cmp(p r,p m)
{
return r.a<m.a;
}
int cmp2(p r,p m)
{
return r.id<m.id;
}
int main ()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector <p> op (n+1);
for(int i=1;i<=n;i++)
{
cin>>op[i].a>>op[i].b>>op[i].c;
op[i].id=i;
}
sort(op.begin(),op.end(),cmp);
ll now=0;
for(int i=1;i<=n;i++)
{
if(op[i].a>=now)
{
now=op[i].a+op[i].c;
op[i].d=now;
}
else
{
now=op[i].c+now;
op[i].d=now;
}
}
op[0].e=0;
for(int i=1;i<=n;i++)
{
ll ans=0;
if(i>10)
{
if(op[i].b>op[i-10].e)
{
op[i].e=op[i].b;
}
else
{
op[i].e=op[i-10].e;
ans=ans+op[i-10].e-op[i].b;
}
}
else
{
op[i].e=op[i].b;
}
if(op[i].b+ans<op[i].d)
{
ans=ans+(op[i].d-(op[i].b+ans));
}
op[i].an=ans;
}
sort(op.begin(),op.end(),cmp2);
for(int i=1;i<=n;i++)
{
cout<<op[i].an<<" ";
}
cout<<endl;
}
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

人满为患
https://www.xiaobaibai454.top/posts/study-26-11-14-2/
作者
Xiao_baibai
发布于
2026-11-14
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录