div.2
拿一个数组保存播放记录，然后按照操作模拟做，就好啦。为了方便处理，我把第一首歌永久固定在了播放记录的第一项。
1 #include2 #include 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\n",list[tot - 1] + 1);34 }35 }36 }
div.1
这个题我是用std::set来做的。所以把这个题当作std::set的推广(雾。
维护一个车站的集合，以及一个相邻车站间距离的集合。
插入和删除，就相应在车站集合里插入/删除，然后更新一下相邻车站间距离的集合。
询问的话，输出车站间距离的集合的最小值即可。
然后距离可能会有一样的，所以维护距离得使用std::multiset(多重集)。
更多的关于set的信息，可以移步看，关于multiset的信息，可以看。或者百度也行。
时间复杂度O(nlogn)。
1 #include2 #include 3 4 std::set set; 5 std::multiset dis; 6 7 void add(int x) { 8 if (set.find(x) != set.end()) return ; 9 std::set ::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 ::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 ::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 ::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\n",*dis.begin());61 }62 }63 }64 }65 }