MUSICAL CHAIRS
時間限制: 1 Sec 內存限制: 128 MB
提交: 386 解決: 76
[提交] [狀態] [命題人:admin]
題目描述
Musical chairs is a game frequently played at children’s parties. Players are seated in a circle facing outwards. When the music starts, the players have to stand up and move clockwise round the chairs. One chair is removed, and when the music stops the players all have to try to sit down on one of the chairs. The player who does not manage to sit down is out, and the game continues until there is just one player left, who is the winner.

輸入
The first line contains a single integer, N which is the number of players (1 < N <= 15).
The next N lines have the names of the players.
The next line contains R, an integer which tells how many rounds are to be processed (0 < R < N). The next R lines each contain a pair of integers S and M, separated by a space. S is the number of the seat to be removed. Seats are numbered from 1 to the number of seats remaining in a clockwise direction.
M is the number of moves made before the music stops (0 < M <= 30). A move takes a player from one seat to the next in a clockwise direction. A move from the highest seat number takes a player to seat 1.

輸出
After each round has taken place, output a line
has been eliminated.
where is the name of the person who does not find a seat. This will be the person who would have ended up at the seat which was removed.
At the end of the specified number of moves, output a line which either says
has won.
where a single player remains, or
Players left are .
where the game is not yet finished.
contains the name of each player not yet eliminated in the same order as in the input. The names are separated by spaces.

樣例輸入
復制樣例數據
5
Anne
Bill
Chen
Di
Everet
4
3 6
2 8
1 5
2 6
樣例輸出
Bill has been eliminated.
Anne has been eliminated.
Chen has been eliminated.
Everet has been eliminated.
Di has won.

題目大意：
先輸入一個數字$n$，代表有$n$個人參加游戲，其下$n$行輸入每個參與者的名字，從$1$到$n$依次編號，然后這$n$個人圍繞$n$個凳子旋轉，每回合將抽掉一個凳子，而這代表著將有一個人被淘汰，在每回合中，所有人繞著凳子順時針旋轉，且每回合都將凳子重新從$1$開始編號。其后先輸入一個數字$t$，代表游戲進行了$t$個回合，對于每回合，輸入兩個整數$r$和$m$，代表此回合抽掉的凳子編號以及玩家旋轉的次數。輸出每回合淘汰掉的人，按照最后剩下的人的個數輸出不同的格式。

解題思路：
此題知道意思后直接模擬即可，我認為用雙端隊列比較好模擬。

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
string str[20];
deque<int> q;
int arr[100];
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int n;cin>>n;string s;rep(i,1,n) {cin>>s;str[i]=s;}lep(i,n,1)q.push_back(i);int t;cin>>t;int r,m;while(t--) {cin>>r>>m;while(m--) {int t=q.front();q.pop_front();q.push_back(t);}rep(k,1,r-1) {int t=q.back();q.pop_back();q.push_front(t);}int num=q.back();q.pop_back();rep(k,1,r-1) {int t=q.front();q.pop_front();q.push_back(t);}cout<<str[num]<<" has been eliminated."<<endl;}int cnt=0;while(!q.empty()) {arr[++cnt]=q.front();q.pop_front();}sort(arr+1,arr+1+cnt);if(cnt>1) {cout<<"Players left are";rep(i,1,cnt) {cout<<" "<<str[arr[i]];}cout<<"."<<endl;}if(cnt==1) {cout<<str[arr[1]]<<" has won."<<endl;}return 0;
}