#A. 选夏令营旗手

【问题描述】

一年一度的江苏省“信息与未来”小学生夏令营活动又开始了。与每年一样，组织者又设计安排了许多有趣的活动，其中第一项依然是挑选本次夏令营的旗手！由于这是一个非常具有荣誉感的角色，所以报名参加夏令营旗手角逐的营员仍然非常多，营委会于是规定：

将N个人排成一排，编号1～N。从第1人开始进行1～M正向报数，报到M的人出列，再从下一个人开始继续1到M报数、出列。（注意：按某个方向报数报到尾部时，再反方向继续报数）。如此进行下去，直到剩下一人为止，这个人就是本次夏令营的旗手。

小明非常渇望能成为旗手，你能编一个程序帮助他实现愿望吗？如果可以的话，你的程序应输出小明的编号。

【输　 入】键盘输入二个整数N，M （2≤N，M≤300，N≥ M ），用一个空格分隔。

【输　 出】一个整数，表示小明在队列中的编号。

【样例输入1】9 3

【样例输出1】8

【样例说明1】出列顺序为：3、6、9、5、1、7、2、4

【样例输入2】8 3

【样例输出2】8

【样例说明2】出列顺序为：3、6、7、2、5、1、4

思路

使用两个栈 dql dqr

初始 9 8 7 。。。 2 1 依此入栈dqr

对dqr依此出栈，计数，达到m舍弃， 否则入dql

dqr处理完成后， 再反过来执行。

Code

#include <bits/stdc++.h>
using namespace std;
#include <vector>
#include <deque>
#include <stack>

int n,m;
stack<int> dql, dqr;


int main(){
    cin>>n>>m;

    for(int i=n; i>=1; i--){
        dqr.push(i);
    }
    
    int mcnt = 0;
    bool rightflag = true;
    
    while(dqr.size()+dql.size() > 1){
        int head = 0;
        if (rightflag){
            head = dqr.top();
            dqr.pop();
        } else {
            head = dql.top();
            dql.pop();
        }

//        cout << "pop one element = " << head << endl;

        mcnt++;
        if (mcnt == m){
//            cout << "out = " << head << endl;
            mcnt = 0;
        } else {
            if (rightflag){
                dql.push(head);
                if (dqr.size() == 0){
                    mcnt--;
                }
            } else {
                dqr.push(head);
                if (dql.size() == 0) {
                    mcnt--;
                }
            }
        }
        
        if (rightflag){
            if (dqr.size() == 0){
                rightflag = false;
            }
        } else {
            if (dql.size() == 0) {
                rightflag = true;
            }
        }
    }
    
    if (dql.size()){
        cout << dql.top() << endl;
    } else {
         cout << dqr.top() << endl;
    }
}