CCF 201709-2 public key box [simulation question]

试题号: 201709-2
试题名: 公钥匙箱
时间限限: 1.0s
Memory limit: 256.0MB
Description of the problem:

问题描述

There is a school teacher sharing NA classroom, according to regulations, all keys must be placed in the public key box, the teacher can not bring the key back Family. Every time the teacher attends class, he finds the key of the class in his class from the public key box to open the door. After finishing the class, put the key back into the key box. The key box has a total of N hooks, arranged in a row from left to right, used to hang N the keys to a classroom. A bunch of keys have no fixed hanging position, but the keys have signs, so the teachers won't mix the keys. Each time the key is taken, the teachers will find the key they need to take it away without moving the other keys. Each time the key is returned, the teacher of the key will find the empty hook on the far left and hang the key on the hook. If there are multiple teachers who still have the keys, they are still in the order of the key number from small to large. If the teacher has the key and the teacher picks up the key at the same time, the teachers will return the key and then take it out. At the beginning of the day, the keys are placed in the key box in order from small to large. There are KThe teacher wants to go to class, give the key that each teacher needs, the time to start the class and the length of the class. It is assumed that the class time is the key time. The order of the keys in the final key box is How was it?

Input format

The first line of input contains two integers NK. Next K, each line of three integers wsc, respectively, indicates the key number that a teacher wants to use, the time to start the class, and the duration of the class. There may be multiple teachers using the same key, but the time the teacher uses the keys does not overlap. To ensure that the input data meets the input format, you do not have to check the legality of the data.

output format

output one line, including N, an integer, separated by a space between adjacent integers, in turn indicating the key number hanging on each hook.

样样输入

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 ≤NK ≤ 10, 1 ≤ w ≤ N, 1 ≤ sc ≤ 30; For 60% of the evaluation cases, 1 ≤ NK ≤ 50,1 ≤ w ≤ N,1 ≤ s ≤ 300,1 ≤ c ≤ 50; For all evaluation use cases, 1 ≤NK ≤ 1000,1 ≤ w ≤ N,1 ≤ s ≤ 10000,1 ≤ c ≤ 100。

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;
}