58同城怎么做网站,wordpress改变后台地址,北京王府井简介,成都的网站建设CSP-201709-2-公共钥匙盒
关键点
1. 选择恰当的数据结构存储钥匙的存取操作
结构体MyKey包含三个字段#xff1a;time、opt和index。
time字段表示操作发生的时间点。对于取钥匙的操作#xff0c;这个时间就是老师上课的开始时间#xff1b;对于还钥匙的操作#xff0c…CSP-201709-2-公共钥匙盒
关键点
1. 选择恰当的数据结构存储钥匙的存取操作
结构体MyKey包含三个字段time、opt和index。
time字段表示操作发生的时间点。对于取钥匙的操作这个时间就是老师上课的开始时间对于还钥匙的操作这个时间是老师上课结束的时间也就是开始时间加上持续时间。opt字段是一个布尔值用于表示是取钥匙还是还钥匙。在我们的案例中我们使用1来表示取钥匙0来表示还钥匙。这个字段对于区分同一时间点发生的不同操作类型很重要。index字段表示钥匙的编号即它对应哪一把钥匙。
2. 按照题目描述的优先级大小排序
题目要求在处理钥匙存取操作时遵循一定的优先级顺序首先按照操作的时间排序如果时间相同则取钥匙的操作应在还钥匙的操作之前处理如果仍然相同则按照钥匙的编号排序。
实现这个需求我们使用自定义的比较函数myCmp来为keyList数组进行排序。这个比较函数遵循以下规则
首先比较time字段。较早的时间应该排在前面。如果time字段相等则比较opt字段。由于我们规定取钥匙1应该在还钥匙0之前所以opt较大的应该排在前面。如果opt也相同则比较index字段即钥匙编号较小的编号排在前面。
这个排序规则确保了我们可以按照题目要求的顺序处理所有的钥匙存取操作。经过排序后我们的算法将按照正确的时间顺序和优先级来模拟每一次钥匙的取还过程从而准确地重现钥匙盒中钥匙的最终状态。
解题思路 输入处理首先代码从标准输入读取两个整数N和K其中N表示钥匙总数和挂钩的数量相同K表示总共有多少个教师需要使用钥匙。然后代码读取接下来的K行输入每行包含三个整数w, s, c分别代表一位老师使用的钥匙编号、上课开始的时间和上课的时长。 初始化钥匙盒状态初始化一个名为box的整数向量大小为N代表钥匙盒的状态。初始状态下钥匙是按照编号从小到大顺序排列的即box[i] i 1。 构造时间线对于每一位老师记录两个时间点取钥匙的时间和还钥匙的时间。这是通过构造一个结构体数组keyList来实现的每个结构体元素记录了时间点、操作类型取还和钥匙编号。其中opt字段用于区分是取钥匙1还是还钥匙0。 时间线排序使用自定义的比较函数myCmp对keyList进行排序。排序规则是首先按时间点排序如果时间点相同则取钥匙的操作排在还钥匙的操作之后如果还存在相同则按钥匙编号进行排序。 模拟钥匙的取还过程遍历排序后的时间线根据操作类型更新钥匙盒box的状态。如果是还钥匙opt为0找到box中第一个空位置用-1表示并将相应的钥匙编号放在那里。如果是取钥匙opt为1找到钥匙盒中对应的钥匙并将其位置设为-1表示钥匙被取走。 输出最终钥匙盒状态遍历box向量输出每个挂钩上的钥匙编号。这就是最终的钥匙盒状态。
完整代码
#include iostream
#include algorithm
#include vector
using namespace std;struct MyKey
{int time; // 操作时间bool opt; // 0-还 1-取int index; // 钥匙序号
};bool myCmp(MyKey a, MyKey b) { // 优先级操作时间 还/取 序号if (a.time b.time) {if (a.opt b.opt) return a.index b.index;else{if (!a.opt) return true;else if (!b.opt) return false;}}return a.time b.time;
}int N, K, w, s, c;
vectorMyKeykeyList;int main() {cin N K;vectorintbox(N);for (int i 0; i box.size(); i){box[i] i 1;}for (int i 0; i K; i){cin w s c;keyList.push_back({ s,1,w });keyList.push_back({ s c,0,w });}sort(keyList.begin(), keyList.end(), myCmp);for (auto it : keyList) {if (!it.opt) // 还钥匙{for (auto jt : box) {if (jt -1){jt it.index;break;}}}else // 取钥匙{for (auto jt : box) {if (it.index jt){jt -1;break;}}}}for (auto it : box) {cout it ;}return 0;
}文章部分内容参考自CSP公共钥匙盒
