题目的主要信息：

MP3每页只能显示4首歌曲，光标初始的位置为第1首歌
通过上下键控制光标移动来浏览歌曲列表，歌曲总数<=4的时候，不需要翻页，只是挪动光标位置，首尾相接
歌曲总数大于4的时候，特殊翻页：屏幕显示的是第一页（即显示第1 – 4首）时，光标在第一首歌曲上，用户按Up键后，屏幕要显示最后一页（即显示第7-10首歌），同时光标放到最后一首歌上；一般翻页：屏幕显示的不是第一页时，光标在当前屏幕显示的第一首歌曲时，用户按Up键后，屏幕从当前歌曲的上一首开始显示，光标也挪到上一首歌曲。光标当前屏幕的最后一首歌时的Down键处理也类似
进阶要求：时间复杂度 $O (n)$ ，空间复杂度 $O (n)$

方法一：遍历判断

我们遍历命令字符串之前，先设置光标当前位置为1，页首位置（即这一页第一个）为1，然后遍历命令字符串开始移动。

如果命令是向下，光标增加，如果超过了 $n$ ，则光标回到第一个，页首也是。在光标位置大于4且光标位置与页首位置相差大于等3的时候，说明光标移出了页面，页首要跟着向下。

如果命令是向上，与向下类似，先减小光标，再判断是否小于1，小于1去到最后一个，页首也到最后一页。除了光标在最后四个以外，光标只要在页首前面就要更新页首。

最后根据页首输出这一页的元素，当然要区分是否足够4个的情况，当前光标直接输出即可。

具体做法：

#include<iostream>
#include<string>
using namespace std;

int main(){
    int n;
    string orders;
    while(cin >> n >> orders){
        int cur = 1; //光标当前位置
        int begin = 1; //页首位置
        int len = orders.length(); //命令个数
        for(int i = 0; i < len; i++){
            if(orders[i] == 'D'){ //向下
                cur++;
                if(cur > n){ //最后一个回到第一个
                    cur = 1;
                    begin = 1;
                }
                if(cur > 4 && cur >= begin + 3)
                    begin = cur - 3; //更新页首位置
            }
            else{ //向上
                cur--;
                if(cur == 0){ //第一个向上到最后一个
                    cur = n; 
                    begin = cur - 3; //更新页首位置
                }
                if(cur < n - 3 && cur == begin - 1)
                    begin = cur; //更新页首位置
            }
        }
        if(n >= 4){ //大于4个，一页输出4个
            cout << begin << " " << begin + 1 << " " << begin + 2 << " " << begin + 3;
        }else{ //小于4个，全部输出
            for(int i = 1; i <= n; i++)
                cout << i << " ";
        }
        cout << endl << cur << endl; //输出当前位置
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m)$ ，其中 $m$ 为命令字符串的长度，遍历整个字符串，与歌曲数量 $n$ 无关
空间复杂度： $O (1)$ ，直接判断，无额外空间

方法二：双向队列

具体做法：

我们也可以用一个长度为n（当不足4个元素时）或者长度为4的双向队列来表示选中的页。

遍历字符串，根据每个字符对队列进行操作：如果是向下移动，先判断是否到了最后一个，如果是则回到第一个，且清空队列，将前面几个加入队列。否则光标直接增加，查找增加后的光标是否在队列中，如果不在将其加入队尾，超过4的队列弹出队首；如果是向上移动，先判断是否到了第一个，如果是则去到最后一个，且清空队列，将最后几个加入队列。否则光标直接减少，查找减少后的光标是否在队列中，如果不在将其加入队首，超过4的队列弹出队尾。

最后队列中的元素就是当前页的元素。

alt

#include<iostream>
#include<string>
#include<deque>
#include<algorithm>
using namespace std;

void operat(deque<int>& dq, char c, int& cur, int n){
    if(c == 'D'){ //向下移动
        if(cur == n){ //如果当前是最后一个
            dq.clear();
            cur = 1; //移动到第一个
            if(n >= 4){ //双向队列清空，更新为前面4个或者n个
                for(int i = 1; i <= 4; i++)
                    dq.push_back(i);
            }else{
                for(int i = 1; i <= n; i++)
                    dq.push_back(i);
            }
        }else{
            cur++; //当前光标向下
            if(find(dq.begin(), dq.end(), cur) == dq.end()) //如果当前光标不在队列中
                dq.push_back(cur); //加入队列尾
            if(dq.size() > 4) //队列大于4
                dq.pop_front(); //弹出队首
        }
    }else{ //向上移动
        if(cur == 1){ //如果当前是第一个
            dq.clear();
            cur = n; //移动到末尾
            if(n >= 4){ //双向队列清空，更新为后面4个或者n个
                for(int i = n; i > n -  4; i--)
                    dq.push_front(i); 
            }else{
                for(int i = n; i > 0; i--)
                    dq.push_front(i);
            }
        }else{
            cur--;  //当前光标向上
            if(find(dq.begin(), dq.end(), cur) == dq.end())  //如果当前光标不在队列中
                dq.push_front(cur);  //加入队列首
            if(dq.size() > 4) //队列大于4
                dq.pop_back();  //弹出队尾
        }
    }
}

int main(){
    int n;
    string orders;
    while(cin >> n >> orders){
        deque<int> dq; //大小为4或者n的双向队列记录当前页
        int cur = 1;
        for(int i = 0; i < orders.length(); i++) //根据每个命令维护双向队列
            operat(dq, orders[i], cur, n);
        for(int i = 0; i < dq.size(); i++) //输出双向队列的元素
            cout << dq[i] << " ";
        cout << endl << cur << endl; 
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m)$ ，遍历字符串的复杂度，队列最长不超过4，常数操作时间
空间复杂度： $O (1)$ ，队列最长不超过4，常数空间

题解 | #MP3光标位置#

题目的主要信息：

方法一：遍历判断

方法二：双向队列