文档章节

PAT1014. Waiting in Line

d
 dream启程
发布于 2014/04/12 11:00
字数 462
阅读 199
收藏 0
PAT

第一次写的

 #include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int id;
    int time;
    int end_time;
}cut[1005];
queue<int> Q[25];
int Q_curtime[25];//window endtime
int qur_id[1005];
void transaction(int n,int m,int k)
{
    int Nm=n*m;
    memset(Q_curtime,0,sizeof(Q_curtime));
    int i;
    for(i=0;i<Nm&&i<k;i++){
            Q[i%n].push(i);
    }
    for(;i<k;i++){
        Q[n].push(i);
    }
    int havedelCut=0;
    while(havedelCut<k){
            int min_time=123456789,min_id=0,id;//
            for(int i=0;i<n;i++){
                if(!Q[i].empty()){
                    id=Q[i].front();
                    if(cut[id].time+Q_curtime[i]<min_time){
                        min_id=i;
                        min_time=cut[id].time+Q_curtime[i];
                    }
                }
            }
            id=Q[min_id].front();
            Q_curtime[min_id]+=cut[id].time;
            cut[id].end_time=Q_curtime[min_id];
            Q[min_id].pop();
            ++havedelCut;
            if(Q[min_id].size()<m){//customer less m
                if(!Q[n].empty()){
                    Q[min_id].push(Q[n].front());
                    Q[n].pop();
                }
            }
    }
}
int main()
{
    int n,m,k,q;
    scanf("%d %d %d %d",&n,&m,&k,&q);
    for(int i=0;i<k;i++){
        scanf("%d",&cut[i].time);
    }
    for(int i=0;i<q;i++){
        scanf("%d",&qur_id[i]);
    }
    transaction(n,m,k);
    for(int i=0;i<q;i++){
        int endtime=cut[qur_id[i]-1].end_time;
        if(endtime-cut[qur_id[i]-1].time<540)
            printf("%02d:%02d\n",8+endtime/60,endtime%60);
        else
            printf("Sorry\n");
    }
    return 0;
}

参考别人代码有改进的

 #include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x6fffffff
struct node
{
    int time;
    int end_time;
}cut[1005];//customer
queue<int> Q[25];//window queue
int Q_curtime[25];//window endtime
void transaction(int n,int m,int k)
{
    int Nm=n*m;
    memset(Q_curtime,0,sizeof(Q_curtime));
    int i;
    for(i=0;i<Nm && i<k;i++)
    {
            cut[i].end_time=Q_curtime[i%n]+cut[i].time;
            Q_curtime[i%n]=cut[i].end_time;
            Q[i%n].push(i);
    }
    for(;i<k;i++)
    {
            int mmin = INF;
            int id=-1;
            for(int j=0;j<n;j++){
                int topid=Q[j].front();
                if(mmin>cut[topid].end_time)
                {
                    id=j;
                    mmin=cut[topid].end_time;
                }
            }
            Q[id].pop();
            cut[i].end_time=Q_curtime[id]+cut[i].time;
            Q_curtime[id]=cut[i].end_time;
            Q[id].push(i);
    }
}
int main()
{
    int n,m,k,q;
    scanf("%d %d %d %d",&n,&m,&k,&q);
    for(int i=0;i<k;i++){
        scanf("%d",&cut[i].time);
        cut[i].end_time=INF;
    }
    transaction(n,m,k);
    for(int i=0;i<q;i++){
        int id;
        scanf("%d",&id);id--;
        int  endtime=cut[id].end_time;
        if(endtime-cut[id].time<540)//attention servertime
            printf("%02d:%02d\n",8+endtime/60,endtime%60);
        else
            printf("Sorry\n");
    }
    return 0;
}

© 著作权归作者所有

d
粉丝 2
博文 8
码字总数 1900
作品 0
浦东
程序员
私信 提问
PTA (Advanced Level)1014 Waiting in Line

Waiting in Line   Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for th......

suvvm
2018/12/17
0
0
PAT 1017 Queueing at Bank(排序+优先队列)

版权声明:转载请告知博主并要注明出处嗷~ https://blog.csdn.net/AkatsukiItachi/article/details/84073043 PAT1017 1017 Queueing at Bank (25 分) Suppose a bank has K windows open ......

语海与冰
2018/11/14
0
0
POJ 3481 Double Queue(set实现)

Double Queue   The new founded Balkan Investment Group Bank (BIG-Bank) opened a new office in Bucharest, equipped with a modern computing environment provided by IBM Romania,......

suvvm
2018/10/31
0
0
ORACLE如何清除OEM下的历史警告信息

ORACLE10G如何清除OEM下的历史警告信息 问题描述:OEM的HOME页面可以显示ORACLE的报警信息,但报警事件清除后该信息不会自动清除。随着时间的增长,信息量逐渐加大,解决方法是手工予以清除。...

rudy_gao
2014/07/02
0
0
SOJ1114(历史排名第130)

2017-11-17的排名 虽然用C可能会更快,但是这不是算法上的改良,所以这样改了没啥意义。 具体的题目就是这样的啦~ 1114. Food Cubes Constraints Time Limit: 10 secs, Memory Limit: 32 MB...

肥宅_Sean
2017/11/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
10
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0
PHP+Ajax微信手机端九宫格抽奖实例

PHP+Ajax结合lottery.js制作的一款微信手机端九宫格抽奖实例,抽奖完成后有收货地址添加表单出现。支持可以设置中奖概率等。 奖品列表 <div class="lottery_list clearfix" id="lottery"> ......

ymkjs1990
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部