队列+猴子分桃

队列+猴子分桃

/*
    输入 5 3 40
    输出 1 3 4 5 2 表示出队顺序 
*/

#include<bits/stdc++.h>
using namespace std;
const int add_length=10;
const int init_length=100;
template<typename ElemType>
struct Qnode{
    Qnode * next;
    ElemType data;
};
template<typename ElemType>
struct MyQueue{
    Qnode<ElemType>* base;
    Qnode<ElemType>* top;
    int len;
    MyQueue(){
        len=0;
        base=new Qnode<ElemType>;
        base->next=NULL;
    }
    void push_back(ElemType x){
        len++;
        Qnode<ElemType>* temp=new Qnode<ElemType>;
        temp->data=x;
        temp->next=base->next;
        if(len==1) top=temp;
        base->next=temp;
    }

    bool empty()
    {
        return base==top;
    }

    void pop(){
        Qnode<ElemType>* temp=base;
        while(temp->next!=top) temp=temp->next;
        top=temp;
    }

    ElemType front(){
        return top->data;
    }

    int size(){
        return len;
    }
};
int n,m,k;

void init()
{
    cin>>n>>k>>m;
}

int peach[2000];

void solve()
{
    int count=0;
    int now=0;
    memset(peach,0,sizeof(peach));
    MyQueue<int>Q;
    for(int i=1;i<=n;i++)
    {
        Q.push_back(i);
    }
    while(!Q.empty()){
        count++;
        if(count==k+1) count=1;
        now+=count;
        //如果当前猴子拿足够了 
        if(peach[Q.front()]+now>=m){
            now=peach[Q.front()]+now-m;
            cout<<Q.front()<<" "; 
            Q.pop();
        }else{
            //如果拿了当前的桃子还不够,则要重新进入队列 
            peach[Q.front()]+=now;
            now=0;
            int temp=Q.front();
            Q.pop();
            Q.push_back(temp);
        }
    }
}

int main()
{
    init();
    solve();
}

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注