试题号: | 201709-2 |

试题名: | 公钥匙箱 |

时间限限: | 1.0s |

Memory limit: | 256.0MB |

Description of the problem: |
问题描述 There is a school teacher sharing Input format The first line of input contains two integers output format output one line, including 样样输入 5 2 4 3 3 2 2 7 样样出 1 4 3 2 5 样例说明 The first teacher started using the key of classroom No. 4 from time 3, using 3 units of time, so at time 6 key. The second teacher started using the key from time 2 and used 7 units of time, so the key was also at time 9. The key status after each critical moment is as follows (X means empty): After time 2 is 1X345; After time 3 is 1X3X5; After time 6 is 143X5; After time 9, it is 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 评价用例比例和约定 For 30% of the evaluation use cases, 1 ≤ |

problem analysis: The question is a simulation question, which can be simulated according to the requirements of the topic. First, according to the start and end time, from small to large, it is stored in two arrays.

The rest of the comments.

```
#include <iostream>
#include <vector>
#include <algorithm>
Using namespace std;
Int n,k;
Struct node{
Int num,start,end;
};
Int m[1005];
/ / Two arrays are sorted according to class time and class time from small to large
Vector<node> vs,ve;
Bool cmp1(node x,node y)
{
Return x.start<y.start;
}
Bool cmp2(node x,node y)
{
If(x.end==y.end)
{
Return x.num<y.num;
}
Else
{
Return x.end<y.end;
}
}
Int findnumber(int key)//find the key
{
For(int i=1;i<=n;i++)
{
If(key==m[i])
{
Return i;
}
}
Return -1;
}
Int main()
{
Cin>>n>>k;
For(int i=0;i<k;i++)
{
Node nn;
Int w,s,c;
Cin>>w>>s>>c;
Nn.num=w;nn.start=s;nn.end=s+c;
Vs.push_back(nn);
Ve.push_back(nn);
}
Sort(vs.begin(), vs.end(), cmp1);
Sort(ve.begin(), ve.end(), cmp2);
For(int i=1;i<=n;i++)
{
m[i]=i;//Initialization Keys are placed in the key box in order from small to large.
}
Int i=0, j=0;
//If the minimum start time is earlier than the minimum end time, then just take the key and take it out. i++
//If the minimum start time is later than the minimum end time, then find the smallest number that is empty and the key is still after j++
While(i<k&&j<k)
{
If(vs[i].start<ve[j].end)//take the key
{
Int key=findnumber(vs[i].num);
m[key]=-1;
i++;
}
Else if(vs[i].start>=ve[j].end)//also key
{
Int key=findnumber(-1);
m[key]=ve[j].num;
j++;
}
}
While(j<k)//Check if the key is all over. If it is not finished yet
{
Int key=findnumber(-1);
m[key]=ve[j++].num;
}
For(int i=1;i<=n;i++)
{
Cout<<m[i]<<" ";
}
Return 0;
}
```