-
First and Foremost
这个题做了挺长时间的，原因是我想不用STL和结构体来解这道题。毕竟这仅是第二道题。可是事实上我低估它了，或者说是因为我的技术还不够——我没有把它figue out。最后我还是下定主意复习一下STL，然后参考了【meelo】大神的【文章】，重新做了这道题。
-
问题描述
| 试题编号： | 201709-2 |
| 试题名称： | 公共钥匙盒 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： | 问题描述 有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。 输入格式 输入的第一行包含两个整数N, K。 输出格式 输出一行，包含N个整数，相邻整数间用一个空格分隔，依次表示每个挂钩上挂的钥匙编号。 样例输入 5 2 样例输出 1 4 3 2 5 样例说明 第一位老师从时刻3开始使用4号教室的钥匙，使用3单位时间，所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙，使用7单位时间，所以在时刻9还钥匙。 样例输入 5 7 样例输出 1 2 3 5 4 评测用例规模与约定 对于30%的评测用例，1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30； |
-
解题代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct teacher{int time;//取/还时间点。int fetchOrReturn;//1为取；0为还.int keyNum;//钥匙编号。teacher(int t, bool f, int k):time(t), fetchOrReturn(f), keyNum(k){}//用参数列表的形式赋值。bool operator <(teacher tea){//重载"<"运算符。if(time < tea.time) return true;else if(time == tea.time && fetchOrReturn < tea.fetchOrReturn) return true;//先还后取。else if(time == tea.time && fetchOrReturn == tea.fetchOrReturn && keyNum < tea.keyNum)return true;//如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。else return false;}
};
int main()
{int totalKeys, teacherNum;//钥匙串数量，教师数量。cin>>totalKeys>>teacherNum;vector<teacher> teachVec;//使用vector记录教师取/还钥匙的信息。for(int i = 0; i < teacherNum; i++){int key, startTime, endTime;cin>>key>>startTime>>endTime;teachVec.push_back(teacher(startTime, 1, key));teachVec.push_back(teacher(startTime+endTime, 0, key));}sort(teachVec.begin(), teachVec.end());//快速排序。int keyArray[totalKeys + 1];//钥匙串序列。for(int i = 1; i <= totalKeys; i++){keyArray[i] = i;//默认是升序排列。}for(int i = 0; i < teachVec.size(); i++){if(teachVec[i].fetchOrReturn == 1){//1为取钥匙串。for(int j = 1; j <= totalKeys; j++){if(teachVec[i].keyNum == keyArray[j]){keyArray[j] = 0;//将钥匙串取走。break;}}}else{//还钥匙串。for(int j = 1; j <= totalKeys; j++){if(keyArray[j] == 0){keyArray[j] = teachVec[i].keyNum;break;}}}}for(int i = 1; i <= totalKeys; i++){//打印输出。cout<<keyArray[i]<<" ";}
}
-
思路分析
使用STL中的vector向量容器存放【取钥匙串/放钥匙串】的序列。将这一序列进行sort快速排序。根据排序后的结果对钥匙串序列进行修改。
-
经验总结
能使用STL的话，尽量用。在之前使用过Java中的容器，很好用。本来因为c++中的容器参数太多，不好记，所以不想用。但是现在看来，想多了。STL真香。
【引用罗茜大神的话】C++中的sort函数：其实有时候sort函数比qsort函数还要稍微快那么一点，它使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)，并且用起来比较方便，有排序用sort函数，不能用创造机会也要用！
头文件：#include<algothrim>
调用参数：sort(排序首地址，排序末地址，定义排序方式的函数名(可有可无))，如果没有排序方式默认按照升序排列。
现在我们就解决一下如何按照降序方式排列。
1,对int型数组a[n]降序排：
bool cmp (int a, int b)
{
return a > b;
}//降序
2,对string型的数组a[n]排序：
bool cmp (string a, string b)
{
return a > b;
}//降序
3,对结构体型的数组a[n]排序：
bool cmp (node a, node b)
{
return a.x > b.x;
}//降序
ps：如果对结构体进行二级排序，只需在排序函数里面加上if语句。
以上所有的排序函数调用的时候都是用：sort(a, a+n, cmp);