CCF 2017 09-02 公共钥匙盒
1.用快速排序函数结合排序规则函数来给取放排序。
2.vector数组的强大功能。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
int num;//钥匙的编号
int start;//动作开始时间
int action;//动作的类型 0:放 1:取
node(){
}
node(int num,int start,int action):num(num),start(start),action(action){
}
}; bool cmp(node a,node b)
{
if(a.start != b.start) return a.start<b.start;///1.按照动作开始时间升序排列
else{
///2.如果时间相同，则先放后取
if(a.action != b.action) return a.action < b.action;
else{
///3.如果时间相同且操作相同，则按照钥匙编号升序排队
return a.num<b.num;
}
}
} int main()
{
int n,k;
while(cin>>n>>k)
{
vector<node> V;
vector<int> state(n+);
for(int i=;i<=n;i++) state[i] = i;
for(int i=;i<k;i++)
{
int num,start,len;
cin>>num>>start>>len;
V.push_back(node(num,start,));//取走钥匙
V.push_back(node(num,start+len,));
} ///按照起始时间升序排列
sort(V.begin(),V.end(),cmp); for(int i=;i<V.size();i++)
{
node u = V[i];
if(u.action == )//取走钥匙操作
{
for(int i=;i<=n;i++)
if(state[i] == u.num)
{
state[i] = -;break;
}
}else{
for(int i=;i<=n;i++)
if(state[i] == -)
{
state[i] = u.num;break;
}
}
} for(int i=;i<=n;i++)
{
cout<<state[i];
if(i==n) cout<<endl;
else cout<<" ";
}
}
return ;
}
Python：
N, K = list(map(int, input().split()))
class node(object):
def __init__(self, num, time, action):
self.num, self.time, self.action = num, time, action
# action: 1代表取，0代表放 mlist = []
for i in range(K):
n1, n2, n3 = list(map(int, input().split()))
mlist.append(node(n1, n2, 1)) # 取
mlist.append(node(n1, n2 + n3, 0)) # 放 keyarr = [(i+1) for i in range(N)] # 将list进行排序，规则为
# 1. 按照时间升序
# 2. 时间相同，按照先放后取，即action升序
# 3. time和action相同，按照钥匙编号num升序
mlist.sort(key=lambda x:(x.time, x.action, x.num)) # 按照排序后的list进行操作
for i in range(2*K):
# print(mlist[i].time, mlist[i].action, mlist[i].num,)
if mlist[i].action == 1: # 取
keyarr[keyarr.index(mlist[i].num)] = -1
else:
for j in range(N):
if keyarr[j] == -1:
keyarr[j] = mlist[i].num
break for i in range(N):
print(keyarr[i], end="\t")