所谓的日常 #6

div.2

FZU 2091 播放器

拿一个数组保存播放记录，然后按照操作模拟做，就好啦。为了方便处理，我把第一首歌永久固定在了播放记录的第一项。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 const int N = 10000 + 5;
 5 int list[N];
 6 int n,m,tot;
 7 
 8 int main() {
 9     int cas;
10     scanf("%d",&cas);
11     while (cas--) {
12         scanf("%d%d",&n,&m);
13         tot = 0;
14         list[tot++] = 0;
15         while (m --) {
16             char str[5];
17             scanf("%s",str);
18             if (strcmp(str,"PRE") == 0) {
19                 if (tot > 1) {
20                     tot --;
21                 }
22             } else if (strcmp(str,"PLAY") == 0) {
23                 int x;
24                 scanf("%d",&x); x --;
25                 if (x != list[tot - 1])
26                     list[tot++] = x;
27             } else {
28                 if (list[tot - 1] != n - 1) {
29                     list[tot] = list[tot - 1] + 1;
30                     tot ++;
31                 }
32             }
33             printf("%d
",list[tot - 1] + 1);
34         }
35     }
36 }

View Code

div.1

FZU 2022 车站

这个题我是用std::set来做的。所以把这个题当作std::set的推广(雾。

维护一个车站的集合，以及一个相邻车站间距离的集合。

插入和删除，就相应在车站集合里插入/删除，然后更新一下相邻车站间距离的集合。

询问的话，输出车站间距离的集合的最小值即可。

然后距离可能会有一样的，所以维护距离得使用std::multiset(多重集)。

更多的关于set的信息，可以移步看这里，关于multiset的信息，可以看这里。或者百度也行。

时间复杂度O(nlogn)。

 1 #include <stdio.h>
 2 #include <set>
 3 
 4 std::set<int> set;
 5 std::multiset<int> dis;
 6 
 7 void add(int x) {
 8     if (set.find(x) != set.end()) return ;
 9     std::set<int>::iterator right = set.lower_bound(x);
10     if (right != set.end()) {
11         dis.insert(*right - x);
12     }
13     if (right != set.begin()) {
14         std::set<int>::iterator left = right;
15         left --;
16         dis.insert(x - *left);
17         if (right != set.end()) {
18             dis.erase(dis.find(*right - *left));
19         }
20     }
21     set.insert(x);
22 }
23 
24 void del(int x) {
25     if (set.find(x) == set.end()) return ;
26     set.erase(x);
27     std::set<int>::iterator right = set.lower_bound(x);
28     if (right != set.end()) {
29         dis.erase(dis.find(*right - x));
30     }
31     if (right != set.begin()) {
32         std::set<int>::iterator left = right;
33         left --;
34         dis.erase(dis.find(x - *left));
35         if (right != set.end()) {
36             dis.insert(*right - *left);
37         }
38     }
39 }
40 
41 int main() {
42     int n;
43     while (scanf("%d",&n) == 1) {
44         set.clear();
45         dis.clear();
46         while (n--) {
47             char str[4];
48             int x;
49             scanf("%s",str);
50             if (str[0] == 'a') {
51                 scanf("%d",&x);
52                 add(x);
53             } else if (str[0] == 'd') {
54                 scanf("%d",&x);
55                 del(x);
56             } else {
57                 if (dis.empty()) {
58                     puts("0");
59                 } else {
60                     printf("%d
",*dis.begin());
61                 }
62             }
63         }
64     }
65 }

View Code