zcmu 1577 食堂的蛋饼（思维）-白红宇

zcmu 1577 食堂的蛋饼（思维）

阅读量：3899 次

发布时间：2019-05-23

本文共 2204 字，大约阅读时间需要 7 分钟。

【题目】

1577: 食堂的蛋饼

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 52 Solved: 10

[][][]

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

506:30 1 206:32 2 406:31 1 306:33 1 506:34 1 1

Sample Output

06:41

【题意】

给定n个人到食堂的时间和早餐的选择和数量，最后一行输入小明的数据，输出小明买好早饭的时间。

早餐从6.30开始供应，初始蛋饼有10个，每隔10分钟做出10个蛋饼，而包子无限量。一个学生需要花费1分钟来完成购买。

【思路】

首先，我们需要考虑到给定的时间不一定有序，所以定义一个结构体存数据并按照时间升序排序。其次，考虑到可能会有在小明之前到食堂买蛋饼的同学面临供应量不足的尴尬，我们需要定义一个vector容器存储等待的同学，并且让买包子的同学优先购买。最后，我们按照时间顺序处理一个个来买早餐的同学，每十分钟增加十个蛋饼，若供应量充足则顺延，否则记录状态使得后边买蛋饼的同学不能优先购买，如果处理到小明就跳出循环~

昨天看了题之后脑子乱乱的，有点思路但是实现起来有点困难。今天看了学长的代码，按照时间处理就使得代码实现起来相当清晰，哲神就是强。

【代码】

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define go(i,a,b) for(int i=a;i<=b;i++)#define og(i,a,b) for(int i=a;i>=b;i--)#define mem(a,b) memset(a,b,sizeof(a))#define Pi acos(-1)#define eps 1e-8using namespace std;typedef long long int ll;const int maxn=1e5+5;const int inf=0x3f3f3f3f;const int mod=1e9+7;struct p{ int t,k,s,id;}f[200];bool cmp(p a,p b){ return a.t
                
                  vec; go(i,1,n) { scanf("%d:%d%d%d",&x,&y,&f[i].k,&f[i].s); f[i].t=x*60+y; f[i].id=i; } sort(f+1,f+n+1,cmp); int sum=0,l=1; go(i,390,24*60) { if(i%10==0) sum+=10; while(i>=f[l].t&&l<=n) vec.push_back(f[l++]); if(vec.size()) { int f=0; go(j,0,vec.size()-1) { if(vec[j].k==2) { if(vec[j].id==n) { printf("%02d:%02d\n",(i+1)/60,(i+1)%60); goto out; } vec.erase(vec.begin()+j); break; } else if(vec[j].k==1&&f==0) { f=1; if(sum>=vec[j].s) { if(vec[j].id==n) { printf("%02d:%02d\n",(i+1)/60,(i+1)%60); goto out; } sum-=vec[j].s; vec.erase(vec.begin()+j); break; } } } } } out:; }}

你可能感兴趣的文章

STL map映照容器（一）map创建、元素插入、元素删除和遍历访问