题目链接:
1.luogu
2.codeforces

set的用法

这道题我用了set,貌似暴力也能过(但是我没测试)。

简单的讲解一下set吧 首先,众所周知,set是自动排序的,并且默认是从小到大排序

  1. se.begin() set开头的指针,也就是set里最小的那个元素的指针
  2. se.rbegin() set反向开头的指针,也就是set里最大的那个元素的指针

这个程序不需要使用到这两行代码

1
2
set<int>::iterator it;
set<int>::reverse_iterator rit;

原因在于我们只需要知道头部和尾部,中间的那部分对答案无关。

代码原理:

  1. 首先开一个book数组记录这个房间是否有人(其实也不用,仍在set里的数字代表着这个房间里面没有人,否则就代表着有人,为方便输出)
  2. 建立一个set,记录这个房间是否有人(意味着所有房间均没有人)
  3. 若输入一个L就把最左边的房间设为有人(即删除se.begin()f[se.begin()]=1
  4. 若输入一个R就把最右边的房间设为有人(即删除se.rbegin()f[se.rbegin()]=1
  5. 若输入一个数字就将房间设为无人(即执行se.insert(s[i]-'0')f[s[i]-'0']=0)
  6. 最后输出book数组即可

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int n;
bool f[15];
string s;
set<int> se;
int main() {
scanf("%d",&n);
cin>>s;
for(int i=0;i<10;i++)
se.insert(i);
int tmp;
for(int i=0;i<s.size();i++) {
if(s[i]=='L') {
tmp=*se.begin();
se.erase(tmp);
f[tmp]=1;
}
else if(s[i]=='R') {
tmp=*se.rbegin();
se.erase(tmp);
f[tmp]=1;
}
else {
tmp=s[i]-'0';
se.insert(tmp);
f[tmp]=0;
}
}
for(int i=0;i<10;i++)
printf("%d",f[i]);
return 0;
}