题解 UVA133 【救济金发放】

_CHO · 2021-06-28 00:58:43 · 题解

好像还没有环状链表解法？

那我来一发

已经颓废到爆切橙题了

看到题目模型是一个圆，而且我们只关心每一个人的前驱和后继，所以容易想到环状链表。两个官员选人直接在链表上暴力跳就可以了。

需要注意几个点：

• 如果两个官员选中的是同一个人，那么只需要输出一次，除此之外还有很uva的输出格式，所以我们可以开一个vector把两个官员每次选出的人存起来，最后一起输出。

• 以A官员为例，第一轮时， A 官员走 k 步，需要注意的是，第一个人是包括在这 k 步之内的。也就是说，在第一轮选人的过程中，A官员选出的是 k 号，而不是 k+1 号。这一步的预处理体现在代码中。 B 官员同理。

• 另外就是多测清空这档子事。

#include <bits/stdc++.h>
using namespace std;
int n,p,q,cnt;
int fir,sec;
int val[30],la[30],ne[30];
vector <pair<int,int> > V;

inline void init(){
    cnt=0;
    fir=n;sec=1;
    V.clear();
}
inline void make_list(){
    for(register int i=1;i<=n;++i){
        val[i]=i;
        la[i]=i-1;
        ne[i]=i+1;
    }
    la[1]=n;
    ne[n]=1;
}
inline void print(){
    for(register int i=0;i<V.size();++i){
        if(V[i].first==V[i].second){
            cout<<setw(3)<<V[i].first;
        }else{
            cout<<setw(3)<<V[i].first<<setw(3)<<V[i].second;
        }
        if(i!=V.size()-1) printf(",");
    }
    puts("");
}
int main(){
    while(scanf("%d%d%d",&n,&p,&q)&&(n&&p&&q)){
        init();
        make_list();
        while(cnt<n){
            for(register int i=1;i<=p;++i){
                fir=ne[fir];
            }
            for(register int i=1;i<=q;++i){
                sec=la[sec];
            }
            V.push_back(make_pair(val[fir],val[sec]));
            cnt+=2-(fir==sec);
            ne[la[fir]]=ne[fir];la[ne[fir]]=la[fir];
            ne[la[sec]]=ne[sec];la[ne[sec]]=la[sec];
            fir=la[fir];
            sec=ne[sec];
        }
        print();
    }
    return 0;
}