CCF认证2017092-公共钥匙盒

每行输入的w，s和c实际上代表了两个操作，先是在s时刻将钥匙w取出，再是在s+c时刻将钥匙w放入。由于整个过程是按照时间顺序来进行的，因此可以考虑将每个时刻的具体操作记录下来然后按照时间先后顺序来处理。根据题目的要求，可以设计一个自定义类型来记录每次操作。其属性包括操作时间，操作对象（钥匙编号），操作类型（存或取）。将所有操作按照时间、先存后取和先小后大的次序进行排序。最后按序操作即可得到结果。

具体代码如下：

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

using namespace std;

typedef struct CMD
{
	int time, tp, no; //分别代表操作时刻，操作类型（-1为取，1为放），操作的钥匙
	CMD(int t, int p, int n) : time(t), tp(p), no(n) {}
}CMD;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<CMD> table; //记录操作序列
	vector<int> keys(n + 1); //公共钥匙盒
	iota(keys.begin(), keys.end(), 0);
	for(int i = 0; i < k; i++)
	{
		int key, s, c;
		cin >> key >> s >> c;
		table.push_back(CMD(s,-1,key));
		table.push_back(CMD(s + c, 1, key));
	}
	sort(table.begin(), table.end(), [](const CMD &a, const CMD &b){
		if(a.time == b.time)
		{
			if(a.tp == b.tp) return a.no < b.no;
			return a.tp > b.tp;
		}
		return a.time < b.time;
	}); //排序（类似优先级队列）
	for(auto e : table) //先放再取
	{
		if(e.tp > 0) //放钥匙
		{
			for(unsigned i = 1; i < keys.size(); i++)
			{
				if(keys[i] == 0) { keys[i] = e.no; break; }
			}
		}
		else //取钥匙
		{
			for(unsigned i = 1; i < keys.size(); i++)
			{
				if(keys[i] == e.no) { keys[i] = 0; break; }
			}
		}
	}
	for(unsigned i = 1; i < keys.size(); i++)
		cout << keys[i] << ' ';
	return 0;
}

CCF认证2017092-公共钥匙盒

相关推荐