第三代半导体 网络视频直播系统 Jmeter 微信商家收款 swing oop menu jboss camera Select2 Movejs vue社区 vue学习教程 河南网络推广 photoshop cs3 教程 pytorch安装教程 matlab中不等于怎么表示 flutter ui构建工具 java的string java方法的重载 java类的继承 java手册 java文件路径 java怎么输出数组 谷歌地球打不开 id解锁大师 cg模宝 飞猪ip 神剪辑教程 彩虹岛小草黑暗之矛 bz2 司司网吧 lol卡米尔 hyqihei 虚拟声卡驱动 商标查询软件 古特里克的杀生刀 汉仪旗黑字体下载 组合索引 mysql游标
当前位置: 首页 > 学习教程  > 编程语言

CCF-公共钥匙盒

2021/1/28 23:38:36 文章标签:

公共钥匙盒(CCF) 有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥匙回家。每次老师上课前,都从公共钥匙盒里找到自己上课的教室的钥匙去开门,上完课后&a…

  1. 公共钥匙盒(CCF)

有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥匙回家。每次老师上课前,都从公共钥匙盒里找到自己上课的教室的钥匙去开门,上完课后,再将钥匙放回到钥匙盒中。
  钥匙盒一共有N个挂钩,从左到右排成一排,用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置,但钥匙上有标识,所以老师们不会弄混钥匙。
  每次取钥匙的时候,老师们都会找到自己所需要的钥匙将其取走,而不会移动其他钥匙。每次还钥匙的时候,还钥匙的老师会找到最左边的空的挂钩,将钥匙挂在这个挂钩上。如果有多位老师还钥匙,则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙,则老师们会先将钥匙全还回去再取出。
  今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课,给出每位老师所需要的钥匙、开始上课的时间和上课的时长,假设下课时间就是还钥匙时间,请问最终钥匙盒里面钥匙的顺序是怎样的?

【输入形式】

输入的第一行包含两个整数N, K。
  接下来K行,每行三个整数w, s, c,分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙,但是老师使用钥匙的时间不会重叠。
  保证输入数据满足输入格式,你不用检查数据合法性。

【输出形式】

输出一行,包含N个整数,相邻整数间用一个空格分隔,依次表示每个挂钩上挂的钥匙编号。

【样例输入1】

5 2
4 3 3
2 2 7

【样例输出1】

1 4 3 2 5

【样例输入2】

5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9

【样例输出2】

1 2 3 5 4

【样例1说明】

第一位老师从时刻3开始使用4号教室的钥匙,使用3单位时间,所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙,使用7单位时间,所以在时刻9还钥匙。
  每个关键时刻后的钥匙状态如下(X表示空):
  时刻2后为1X345;
  时刻3后为1X3X5;
  时刻6后为143X5;
  时刻9后为14325。

方法一:强模拟,对时间遍历
#include<iostream>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 struct Key{
     int id=0;
     int out,l,in;
 };
 bool cmp(Key key1,Key key2){
     return key1.id<key2.id;
 }
 int main(){
     int n,k;
     cin>>n>>k;
     int box[10100]={0};
     for(int i=1;i<=n;i++){box[i]=i;}
     Key key[k];
     for(int i=0;i<k;i++){
         cin>>key[i].id>>key[i].out>>key[i].l;
         key[i].in=key[i].out+key[i].l;
     }
     sort(key,key+k,cmp);
     
 //循环终止条件好把n与k搞错
 
     for(int time=1;time<=10100;time++){
         //还钥匙
         for(int i=0;i<k;i++){
             if(key[i].in==time){
                 for(int j=1;j<=n;j++){
                     if(box[j]==0){
                         box[j]=key[i].id;
                         break;
                     }
                 }
             }
         }
         //取钥匙
         for(int i=0;i<k;i++){
             if(key[i].out==time){
                 for(int j=1;j<=n;j++){
                     if(box[j]==key[i].id){
                         box[j]=0;
                         break;
                     }
                 }
             }
         }
     }
     
     
     for(int i=1;i<=n;i++){
         cout<<box[i]<<" ";
     }
     
     return 0;
 }
方法二:拆分为多步骤,对每个步骤进行遍历
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct Key{
    int id=0;
    int time;
    int opation;//1还,0取
};
bool cmp(Key key1,Key key2){
    if(key1.time==key2.time){
        if(key1.opation==key2.opation){
            return key1.id<key2.id;
        }
        else{return key1.opation>key2.opation;}
    }
    else{
        return key1.time<key2.time;
    }
}

int main(){
    int n,k;
    cin>>n>>k;
    Key key[2*k];
    int ID,OUT,D;
    for(int i=0;i<k;i++){//分解成两个动作,还和取
        cin>>ID>>OUT>>D;
        key[2*i].id=ID;
        key[2*i].time=OUT;
        key[2*i].opation=0;
        key[2*i+1].id=ID;
        key[2*i+1].time=OUT+D;
        key[2*i+1].opation=1;
    }
    
    int a[n+1];
    int b[n+1];//b是哨兵数组,钥匙b在哪个钩子上
    for(int i=1;i<=n;i++){
        a[i]=i;
        b[i]=i;
    }
    sort(key,key+2*k,cmp);
    
    for(int i=0;i<2*k;i++){//一共k组/还取/动作
        if(key[i].opation==1){//如果是还钥匙
         for(int j=1;j<=n;j++){//找空盒子
            if(a[j]==0){
                a[j]=key[i].id;
                b[key[i].id]=j;
                break;
            }
         }
        }
        else{
        a[b[key[i].id]]=0;
        }
    }
    for(int i=1;i<=n;i++)
    cout<<a[i]<<" ";
   
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_650265.shtml

附件下载

上一篇:D产生冠军

下一篇:小鲨鱼记账系统

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?