当前位置: 代码迷 >> 综合 >> zcmu--1577: 食堂的蛋饼(模拟)
  详细解决方案

zcmu--1577: 食堂的蛋饼(模拟)

热度:36   发布时间:2023-12-26 09:55:05.0

1577: 食堂的蛋饼

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 47  Solved: 7
[Submit][Status][Web Board]

Description

   早饭吃什么,这是一个深奥的问题。学校貌似好吃的也就一个鸡蛋饼,然而学校的蛋饼经常供不应求,就算排在队伍第一无奈蛋饼还在锅里,还是要等,但是站着第(mao)一(keng)不买(la)早(shi)饭是不行的,所以阿姨会让后面的买包子不买蛋饼的同学先来买,等蛋饼出锅了在按正常的队伍卖早饭,一旦蛋饼不够则优先让买包子的买。爱睡懒觉的小明总是来得较晚所以他想知道他如果他来买早饭大概需要排多久的队伍,好知道会不会迟到。

         假设食堂只有一个窗口,从6.30开始供应,初始蛋饼有10个,包子无限量,大厨每隔10分钟可以做出10个蛋饼,因为蛋饼畅销所以大厨一直在做,若供应量够则每个学生需要花费1分钟来完成购买。我们已知今天买早饭的N个学生来的时间ti和买早饭的种类ki(1表示蛋饼,2表示包子)以及数量si(每个学生只卖一种不会同时买包子和蛋饼),现在给出小明来买早饭的时间,种类和数量,请帮忙计算需要排多久的队伍

Input

   多组测试数据

         第一行包括买早饭的人的数量n(1<=n<=180)

         接下来有n行,每行三个数据ti(06:00<=ti<=09:00),ki(1或2),si(1<=si<=100)分别表示来买的人时间种类以及数量,最后一行则表示来的是小明(保证时间没有重复)

Output

  输出小明买好早饭的时间,格式参照输入时间

Sample Input

5

06:30 1 2

06:32 2 4

06:31 1 3

06:33 1 5

06:34 1 1

Sample Output

06:41

【分析】

ppps:最近好像总是在做模拟题的感觉,每次都做的很烦,因为总是做不对。。情况啊思路啊总是搞不拎清,还是得多想多做吧

这道题,感觉做法很巧妙。

  • 按时间遍历,而不是n个人。因为时间的话,每个时间点都只能让一个人进行购买,一个时间点不可能存在两个人购买的情况,所以在遍历的时候,只要这个时间点有人购买,就break掉,进入下一个时间。
  • 小明只是最后一个输入,不是最后一个来的
  • 其他注意的地方见代码注释

【代码】

#include<bits/stdc++.h>
using namespace std;
struct node{int t,k,s;int id;
}a[200];
bool cmp(node x,node y)
{return x.t<y.t;
}
int main()
{int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++){int x,y;scanf("%d:%d%d%d",&x,&y,&a[i].k,&a[i].s);a[i].t=x*60+y;//化成分钟 a[i].id=i;//记录读入的顺序 }sort(a,a+n,cmp);vector<node>wait;int len=0,egg=0;//蛋饼数起始位0 for(int i=390;i<=24*60;i++){while(i>=a[len].t && len<n)wait.push_back(a[len++]);if(i%10==0)egg+=10;//每10分钟出一次蛋饼 if(wait.size())//如果还有人排队 {int flag=0;//标记是否是每次遍历的第一个人 for(int j=0;j<wait.size();j++)//遍历队列 {if(wait[j].k==2)//如果当前人是包子的话,该时刻必然是卖包子的时刻 {if(wait[j].id==n-1)//如果当前人是小明 {i++;printf("%02d:%02d\n",i/60,i%60);goto out;}wait.erase(wait.begin()+j);//该人买完,从队列中删除 break;}else if(wait[j].k==1 && flag==0){/*flag=0时说明时每次遍历的第一个人,如果当前蛋饼数量不够的话在进行下一个人的时候,是要找买包子的,但是下次遍历的时候遇到买蛋饼并且数量足够卖也是不能卖的,这个时候flag=1所以不会执行该语句,他只能等到找到买包子的那个人*/ flag=1;if(wait[j].s<=egg){if(wait[j].id==n-1){i++;printf("%02d:%02d\n",i/60,i%60);goto out;}egg-=wait[j].s;wait.erase(wait.begin()+j);break;}}}}}out: ;}
}