union

union A{
    int i;
   char c;
}a1;

如上的union会选择成员是

  • 一个int i 或
  • 一个char c

sizeof(union …) = sizeof(每个成员)的最大值

存储

  • 所有的成员共享一个空间
  • 同一时间只有一个成员是有效的
  • union的大小是其最大的成员
  • 初始化时会对第一个成员做初始化

union的用处

#include <stdio.h>

typedef union
{
    int i;
    char ch[sizeof(int)];
} CHI;

int main()
{
    CHI chi;
    chi.i = 1234;
    for(int i = 0; i <sizeof(int); i++)
    {
        printf("%02hhX",chi.ch[i]);
    }
    printf("\n");
    return 0;
}

 

运行结果为D2040000

这是为什么呢?

1234转化为16进制结果为00 00 04 D2,由于我使用的机器为基于X86架构的CPU,所以我的机器是一种小端的机器,低位在前高位在后,所以00 00 04 D2实际被存储为D2 04 00 00,所以我们的结果输出为D2040000。

我们可以通过这个方法得到一个整数内部的各个字节,同样也可以得到double等类型内部的各个字节,当我们要做文件操作时,当我们要把一个整数以二进制的形式写到一个文件里去的时候,都可以用这个方法来做读写的中间媒介。

什么是内存对齐?
关于什么是内存对齐,我们先来看几个例子。

struct str1 {
int a;
char b;
double c;
};

sizeof(str1)=16。

struct str2 {
int a;
double b;
char c;
};

sizeof(str2)=24。

struct str3 {
double a;
int b;
char c;
char d;
};

sizeof(str3)=16。

sizeof(str1)=16而sizeof(str2)=24,sizeof(str3)=16。为什么会产生不一样的结果呢?
这是非常简单的一个例子,体现了结构体的内存对齐规则。

 

  1. 结构体变量的起始地址能够被其最宽的成员大小整除
  2. 结构体每个成员相对于起始地址的偏移能够被其自身大小整除,如果不能则在前一个成员后面补充字节
  3. 结构体总体大小能够被最宽的成员的大小整除,如不能则在后面补充字节
  4. 编译器在编译的时候是可以指定对齐大小的,上述说的只是默认情况,在Windows下这个默认值为8,在Linux下这个默认值为4,使用如下语句可以改变这个默认值。#pragma pack(n),其中n为对其大小。

快速计算方法可以总结为两个公式:

公式1:前面的地址必须是后面的地址正数倍,不是就补齐
公式2:整个Struct的地址必须是最大字节的整数倍

注意:

C语言和C++中空类和空结构体的大小
在C++中规定了空结构体和空类的内存所占大小为1字节,因为c++中规定,任何不同的对象不能拥有相同的内存地址。
而在C语言中,空的结构体在内存中所占大小为0。(gcc中测试为0,其他编译器不一定)

为什么要内存对齐?
1.平台原因(移植原因):不是所有的硬件平台都能访问任意地址上的任意数据的;某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常。
2.性能原因:数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于,为了访问未对齐的内存,处理器需要作两次内存访问;而对齐的内存访问仅需要一次访问。

对于字符串,C语言提供了很多函数来帮助我们处理字符串,这些函数都存在于头文件string.h中。

常用的字符串处理函数有:

  • strlen
  • strcmp
  • strcpy
  • strcat
  • strchr
  • strstr

 

strlen

  • size_t strlen(const char *s);
  • 返回s的字符串长度

实现代码如下:

#include<stdio.h>

int myStrLen(const char *str)
{
    int cnt = 0;
    while(str[cnt] != '\0')
    {
        cnt++;
    }
    return cnt;
}
int main(int argc ,char const *argv[])
{
    char line[] = "Hello World";
    printf("strlen=%lu\n",myStrLen(line));
    return 0;
}

 

strcmp

  • int strcmp(const char *s1,const char *s2);
  • 比较两个字符串,返回:
  • 0:s1==s2
  • 大于0:s1>s2
  • 小于0:s1<s2

数组实现代码如下:

#include<stdio.h>
int myStrCmp(const char *str1,const char *str2)
{
    int idx = 0;
    while(str1[idx]== str2[idx] && str1[idx]!='\0'){
        idx++;
    }
    return str1[idx]-str2[idx];
}
int main(int argc ,char const *argv[])
{
    char s1[] = "Hello World";
    char s2[] = "Hello Worle";
    printf("%d\n",myStrCmp(s1,s2));
    return 0;
}

 

指针实现代码如下:

#include<stdio.h>
int myStrCmp(const char *str1,const char *str2)
{
    int idx = 0;
    while(*str1== *str2 && *str1!='\0')
    {
        str1++;
        str2++;
    }
    return *str1-*str2;
}
int main(int argc ,char const *argv[])
{
    char s1[] = "Hello World";
    char s2[] = "Hello Worle";
    printf("%d\n",myStrCmp(s1,s2));
    return 0;
}

 

strcpy

  • char * strcpy(char *restrict dst,const char *restrict src);
  • 把src的字符串拷贝到dst
  • restrict表明src和dst不重叠(C99)
  • 返回dst

复制一个字符串的常用方法

char *dst = (char*)malloc(strlen(src)+1);

strcpy(dst,src);

数组实现代码如下:

#include<stdio.h>

char* myStrCpy(char *dst,char *src)
{
    int idx = 0;
    while(src[idx] != '\0')
    {
        dst[idx] = src[idx];
        idx++;
    }
    dst[idx] = '\0';
    return dst;
}
int main(int argc ,char const *argv[])
{
    char s1[] = "";
    char s2[] = "Hello World";
    myStrCpy(s1,s2);
    printf("%s\n",s1);
    return 0;
}

 

指针实现代码如下:

#include<stdio.h>

char* myStrCpy(char *dst,char *src)
{

    while(*src != '\0')
    {
        *dst = *src;
        dst++;
        src++;
    }
    *dst = '\0';
    return dst;
}
int main(int argc ,char const *argv[])
{
    char s1[] = "";
    char s2[] = "Hello World";
    myStrCpy(s1,s2);
    printf("%s\n",s1);
    return 0;
}

 

strcat

  • char *strcat(char *dst,const char *src);
  • 把src所指向的字符串(包括“\0”)复制到dest所指向的字符串后面(删除*dest原来末尾的“\0”)。
  • 要保证*dest足够长,以容纳被复制进来的*src。*src中原有的字符不变。
  • 返回指向dest的指针。

实现代码:

#include<stdio.h>

char* myStrCat(char *dst,const char *src)
{
    char *temp = dst;
    while(*dst!='\0')
    {
        dst++;
    }
    while(*src!='\0')
    {
        *dst = *src;
        dst++;
        src++;

    }
    *dst = '\0';
    return temp;
}
int main(int argc ,char const *argv[])
{
    char s1[] = "Hello ";
    char s2[] = "World";
    myStrCat(s1,s2);
    printf("%s\n",s1);
    return 0;
}

 

strchr

  • char* strchr(const char *s , char c);
  • 返回首次出现字符c的位置的指针,如果字符串s中不存在字符c则返回NULL。

实现代码:

#include<stdio.h>
char* myStrChr(char *s,char c)
{
    while(*s!='\0' && *s!= c)
    {
        s++;
    }
    return *s==c ? s+1 : NULL;
}
int main(int argc ,char const *argv[])
{
    char s1[] = "Hello World";
    char s2 = 'W';
    char *ptr = myStrChr(s1,s2);
    printf("%s\n",ptr);
    return 0;
}

 

strstr

  • char* strstr(char *str,const char *str2);
  • str1:被查找目标
  • str2:要查找目标
  • 返回值:若str2是str1的子串,则返回str2在str1的首次出现的地址;如果str2不是str1的子串,则返回NULL。

实现代码:

#include<stdio.h>
char* myStrStr(char *s1,const char *s2)
{
    bool flag = false;
    char *temp1 = s1;
    char *temp2 = (char*)s2;
    while(*s1 != '\0' )
    {
        if(*s2 == '\0')
        {
            flag = true;
            break;
        }
        else if(*s1==*s2)
        {
            s1++;
            s2++;
        }
        else
        {
            s1++;
            s1 = ++temp1;
            s2 = temp2;
        }
    }
    if(flag)
    {
        return temp1;
    }
    else return NULL;
}
int main(int argc ,char const *argv[])
{
    char s1[] = "Hello World";
    char s2[] = "Wor";
    char *ptr = myStrStr(s1,s2);
    printf("%s\n",ptr);
    return 0;
}

main函数一般带有参数,如下

int main(int argc ,char const *argv[])

argv[0]是命令本身,当使用Unix的符号链接时,反映符号链接的名字。

#include<stdio.h>
#include<stdlib.h>

int main(int argc ,char const *argv[])
{
    int i;
    for( i = 0; i<argc; i++)
    {
        printf("%d:%s\n",i,argv[i]);
    }
    return 0;
}

 

当使用命令行执行的时候,可以在后面加上参数,程序会读取到后面的参数并保存在argv数组中。

其中argv[0]为命令的名字(可执行程序的名字)。

如果输入数据时,先告诉你个数,然后再输入,要记录每个数据。

C99可以用变量做数组定义的大小,C99之前呢?

int *a = (int*)malloc(n*sizeof(int));
代码如下:

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int number = 0;
    int *a = 0;
    int i = 0;
    printf("输入数量:");
    scanf("%d",&number);
    a = (int*)malloc(number*sizeof(int));
    for( i = 0; i<number; i++)
    {
        scanf("%d",&a[i]);
    }
    for( i = number - 1; i>=0; i--)
    {
        printf("%d ",a[i]);
    }
    free(a);
}

 

malloc()

#include<stdlib.h>

void * malloc(size_t size);

1.向malloc申请的空间的大小是以字节为单位的

2.返回的结果是void*,需要类型转换为自己需要的类型

3.如果申请失败则返回0,或者NULL

 

试一试你的系统能给你多大的空间:

 

#include<stdio.h>
#include<stdlib.h>

int main()
{
    void *p;
    int cnt = 0;
    while(p = malloc(100*1024*1024))
    {
        cnt++;
    }
    printf("分配了%d00MB的空间\n",cnt);
    return 0;
}

 

在我的电脑(64位 WIndows10家庭中文版,4G内存)上只能分配1900M的空间。

下面是来自知乎的讲解:

地址空间限制是有的,但是malloc通常情况下申请到的空间达不到地址空间上限。内存碎片会影响到你“一次”申请到的最大内存空间。比如你有10M空间,申请两次2M,一次1M,一次5M没有问题。但如果你申请两次2M,一次4M,一次1M,释放4M,那么剩下的空间虽然够5M,但是由于已经不是连续的内存区域,malloc也会失败。系统也会限制你的程序使用malloc申请到的最大内存。Windows下32位程序如果单纯看地址空间能有4G左右的内存可用,不过实际上系统会把其中2G的地址留给内核使用,所以你的程序最大能用2G的内存。除去其他开销,你能用malloc申请到的内存只有1.9G左右。

其实,操作系统版本、程序本身大小、乃至的动态/共享库数量和大小、程序栈数量和大小等都会对其造成影响,甚至有些操作系统使用了一种叫做随机地址空间分布的技术(主要是出于安全考虑,防止程序受恶意攻击),使得进程的堆空间变小。

一个由C/C++编译程序占用内存分为以下几个部分
1、栈区(stack)— 由编译器自动分配释放 ,存放函数参数值,局部变量值等。其操作方式类似于数据结构中栈。
2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中堆是两回事,分配方式倒是类似于链表,呵呵。
3、全局区(静态区)(static)—,全局变量和静态变量存储是放在一块,初始化全局变量和静态变量在一块区域, 未初始化全局变量和未初始化静态变量在相邻另一块区域。 – 程序结束后由系统释放。–>分别是data区,bbs区
4、文字常量区 —常量字符串就是放在这里。 程序结束后由系统释放–>coment区
5、程序代码—存放函数体二进制代码。–>code区

而我们的malloc()申请的空间位于堆区,32位操作系统下理论最大可能申请到的空间是4G(内存达到4G且不算操作系统占用的内存时,实际做不到),64位操作系统下基本是根据内存决定的。

 

free()

1.把申请得来的空间还给“系统”

2.申请过的空间最终都应该还

3.只能还申请来的空间的首地址

4.free(0)和free(NULL)没问题,程序什么都不会归还

 

那么,malloc得到的空间是连续的吗?

逻辑地址连续,物理地址可以不连续。

malloc在大多实现中分配得到的内存空间比要求的大,额外空间记录管理信息——分配块的长度。

 

关于malloc(0)

1.来自C99的最权威的解释,malloc(0)是未定义行为:

2.返回一个地址空间是有意义的:为了和free的正常配对

3.malloc(0)的结果依赖实现

 

putchar

  1. int putchar(int c)
  2. 向标准输入写一个字符
  3. 返回写了几个字符,EOF(-1)表示写失败

getchar

  1. int getchar(void)
  2. 从标准输入读入一个字符
  3. 返回类型是int是为了返回EOF(-1)
  4. Windows下 Ctrl+Z表示读入EOF状态
  5. Unix下 Ctrl+D表示读入EOF状态
#include<stdio.h>
#include<stdlib.h>

int main(int argc ,char const *argv[])
{
    int ch;
    while((ch = getchar())!=EOF)
    {
        putchar(ch);
    }
    return 0;
}

 

怀念一起去金山报道的好吉,一个很厉害的女孩子,去金山居然是为了复习考研顺便实习,知道真相的我被惊呆了,很佩服很佩服。怀念半夜跑出来讨论人生的小房子,金山第一实习生能够周末在公司学习到4点半,祝你在百度一切顺利。怀念帮我分析情感问题的金山罗霸,真的是一个极好的人,希望你能够成功的进入香港的大学念研究生,直到现在都还一直在帮我,可能我再也无法带她去长春见你了吧。怀念我的舍友东东童鞋,周末晚上一起上分到4点,PDF部门是真的很强,祝你在腾讯一切顺利。怀念我的另一个舍友鹏哥,在生活上帮助我很多,半夜和我爬到顶楼一起看风景,希望你能追到你的不二,找到更好的工作。怀念母喵,一起下班一起吃鸡一起学喵叫,想起了我曾经给你直播金山生活,想起了你给我送的麦片是真的好吃(真香),还有那天晚上我们一起去屋顶谈论的很多很多事情,没有你和我一起春招我可能真的进不去金山,祝你以后在金山珠海一切顺利,认识你很开心呢,可惜你好像不再理我了。怀念小和子,从湖南大学逃课出来实习还没记处分的一个小伙伴,你好像一直觉得我很强,其实我很弱很弱的啊啊啊!祝你以后在金山武汉的工作一切顺利。怀念西安交大那个不会C++却来了金山C++岗的bihuchao,一个痴迷计算机世界的核动力专业学生,和你膜蛤谈笑风生的日子很开心,一直一直没有像你说的那样看不起你,我从心底里一直都很佩服你的,祝你在百度一切顺利,后会有期。怀念最后没有来金山去深信服实习的广大同学,我的blog找不回来啦,你让我认识了QQ邮箱日历这个神奇的功能,然后大家每天一起相约leetcode,bihuchao刷题速度太恐怖啦,也曾深夜一起谈论过自己喜欢的女孩子,都是悲伤的故事呢,但是你和我的不同是你很强,祝你在腾讯和东东同学一切顺利。怀念徐建华童鞋,一个很可爱很可爱的重庆妹子,春招同时认识了你和你男朋友,可惜你男朋友没有成功拿到金山的offer,最后秋招你们一起去了网易,祝你们以后的人生一帆风顺。

怀念金山的小伙伴,怀念金山的第一实习生梗,怀念金山的海风,怀念金山的华南第一食堂,怀念金山的一切。。。我想念你们啦!

问题描述
  体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排,学号小的排在前面,然后进行多次调整。一次调整小明可能让一位同学出队,向前或者向后移动一段距离后再插入队列。
例如,下面给出了一组移动的例子,例子中学生的人数为8人。
0)初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8;
1)第一次调整,命令为“3号同学向后移动2”,表示3号同学出队,向后移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8;
2)第二次调整,命令为“8号同学向前移动3”,表示8号同学出队,向前移动3名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7;
3)第三次调整,命令为“3号同学向前移动2”,表示3号同学出队,向前移动2名同学的距离,再插入到队列中,新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程,请问,最终从前向后所有学生的学号依次是多少?
请特别注意,上述移动过程中所涉及的号码指的是学号,而不是在队伍中的位置。在向后移动时,移动的距离不超过对应同学后面的人数,如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时,移动的距离不超过对应同学前面的人数,如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
输入格式
  输入的第一行包含一个整数n,表示学生的数量,学生的学号由1到n编号。
第二行包含一个整数m,表示调整的次数。
接下来m行,每行两个整数p, q,如果q为正,表示学号为p的同学向后移动q,如果q为负,表示学号为p的同学向前移动-q。
输出格式
  输出一行,包含n个整数,相邻两个整数之间由一个空格分隔,表示最终从前向后所有学生的学号。
样例输入
8
3
3 2
8 -3
3 -2
样例输出
1 2 4 3 5 8 6 7
评测用例规模与约定
  对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 1000,所有移动均合法。
AC代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int n,m;
    vector<int> a;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    a.push_back(i);
    for(int cas=0;cas<m;cas++)
    {
        int x,y;
        cin>>x>>y;
        vector<int>::iterator it;
        for(it=a.begin();it!=a.end();it++)
            if(*it==x)
            break;
        a.erase(it);
        a.insert(it+y,x);

    }
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;

}

 

问题描述
  请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。
假设一节车厢有20排、每一排5个座位。为方便起见,我们用1到100来给所有的座位编号,第一排是1到5号,第二排是6到10号,依次类推,第20排是96到100号。
购票时,一个人可能购一张或多张票,最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位,则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中(不考虑是否相邻)。
假设初始时车票全部未被购买,现在给了一些购票指令,请你处理这些指令。
输入格式
  输入的第一行包含一个整数n,表示购票指令的数量。
第二行包含n个整数,每个整数p在1到5之间,表示要购入的票数,相邻的两个数之间使用一个空格分隔。
输出格式
  输出n行,每行对应一条指令的处理结果。
对于购票指令p,输出p张车票的编号,按从小到大排序。
样例输入
4
2 5 4 2
样例输出
1 2
6 7 8 9 10
11 12 13 14
3 4
样例说明
  1) 购2张票,得到座位1、2。
2) 购5张票,得到座位6至10。
3) 购4张票,得到座位11至14。
4) 购2张票,得到座位3、4。
评测用例规模与约定
  对于所有评测用例,1 ≤ n ≤ 100,所有购票数量之和不超过100。
AC代码
#include <iostream>
#include<list>
#include<math.h>
using namespace std;
  int main(){
  int n,m,temp,Count;
  int a[200];
  int b[30];

  for(int i=0;i<20;i++){
    b[i]=5;
  }
  for(int i=0;i<100;i++){
    a[i]=1;
  }

  cin>>n;
  while(n--){
    cin>>m;
    Count =m;
    for(int i=0;i<20;i++)
  {
      temp = i;
     if(b[i]>=m){
        break;
     }
     else temp++;
  }
   if(temp==20){
    for(int i=0;i<100;i++)
    if((a[i]==1)&&(Count!=0)){
        cout<<i+1<<" ";
        Count--;
        a[i]=0;
    }



   }
   else{
    for(int j=temp*5;j<temp*5+5;j++){
        if((a[j]==1)&&(Count!=0)){
            a[j]=0;
            cout<<j+1<<" ";
            Count--;
        }
    }
      b[temp] = b[temp] - m;
    cout<<endl;
   }
  }
  }

 

问题描述
  有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥匙回家。每次老师上课前,都从公共钥匙盒里找到自己上课的教室的钥匙去开门,上完课后,再将钥匙放回到钥匙盒中。
钥匙盒一共有N个挂钩,从左到右排成一排,用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置,但钥匙上有标识,所以老师们不会弄混钥匙。
每次取钥匙的时候,老师们都会找到自己所需要的钥匙将其取走,而不会移动其他钥匙。每次还钥匙的时候,还钥匙的老师会找到最左边的空的挂钩,将钥匙挂在这个挂钩上。如果有多位老师还钥匙,则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙,则老师们会先将钥匙全还回去再取出。
今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课,给出每位老师所需要的钥匙、开始上课的时间和上课的时长,假设下课时间就是还钥匙时间,请问最终钥匙盒里面钥匙的顺序是怎样的?
输入格式
  输入的第一行包含两个整数NK
接下来K行,每行三个整数wsc,分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙,但是老师使用钥匙的时间不会重叠。
保证输入数据满足输入格式,你不用检查数据合法性。
输出格式
  输出一行,包含N个整数,相邻整数间用一个空格分隔,依次表示每个挂钩上挂的钥匙编号。
样例输入
5 2
4 3 3
2 2 7
样例输出
1 4 3 2 5
样例说明
  第一位老师从时刻3开始使用4号教室的钥匙,使用3单位时间,所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙,使用7单位时间,所以在时刻9还钥匙。
每个关键时刻后的钥匙状态如下(X表示空):
时刻2后为1X345;
时刻3后为1X3X5;
时刻6后为143X5;
时刻9后为14325。
样例输入
5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9
样例输出
1 2 3 5 4
评测用例规模与约定
  对于30%的评测用例,1 ≤ NK ≤ 10, 1 ≤ w ≤ N, 1 ≤ sc ≤ 30;
对于60%的评测用例,1 ≤ NK ≤ 50,1 ≤ w ≤ N,1 ≤ s ≤ 300,1 ≤ c ≤ 50;
对于所有评测用例,1 ≤ NK ≤ 1000,1 ≤ w ≤ N,1 ≤ s ≤ 10000,1 ≤ c ≤ 100。
AC代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, k, w, s, c, key[1001];


struct Teacher//定义教师结构体
{
    int key;//钥匙编号
    int time;//使用钥匙时间
    int flag;//设置标识符
};

bool cmp(Teacher t1,Teacher t2){
    if(t1.time !=t2.time){
        return t1.time<t2.time;
    }
    else if(t1.flag !=t2.flag){
        return t1.flag >t2.flag;
    }
    else{
        return t1.key < t2.key;
    }
}
int main(){
std::ios::sync_with_stdio(false);
 vector<Teacher> v;//定义结构体向量
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        key[i] = i;
    }
    for(int i=0;i<k;i++)
    {
        cin>>w>>s>>c;
        Teacher t;
        t.key = w;
        t.time = s;
        t.flag = 0;//借
        v.push_back(t);
        t.key = w;
        t.time = s+c;
        t.flag = 1;//归还
        v.push_back(t);
    }
   sort(v.begin(),v.end(),cmp);

   for(int i=0;i<v.size();i++){
    Teacher t = v[i];
    if(t.flag==0)//借钥匙
    {
       for(int j = 1;j<=n;j++){
        if(key[j]==t.key){
            key[j]=0;
            break;
        }
       }

    }
   else {//还钥匙
      for(int j=1;j<=n;j++){
        if(key[j]==0){
            key[j]=t.key;
            break;
        }
      }
   }
   }
   for (int i=1;i<=n;i++){
    cout<<key[i]<<" ";
   }
   cout<<endl;
   return 0;
}