模拟题:
add的时候出现过的则不再添加
close的时候会影响到top
rotate(Prior、Choose)的时候会影响到top
/*===============================================================
* Copyright (C) 2014 All rights reserved.
*
* File Name: hdu5071.cpp
* Author:sunshine
* Created Time: 2014-11-11
*
================================================================*/
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm> using namespace std; #define SUCCESS puts("success.")
#define EMPTY puts("empty.")
#define INVALID puts("invalid priority.")
#define SAME puts("same priority.")
#define OUT_OF_RANGE puts("out of range.")
#define NO_SUCH_PERSON puts("no such person.") const int MAXN = ; struct Node{
int value;
long long word_num;
void set(int t_value){
value = t_value;
word_num = ;
}
}node[MAXN]; int top_u;// -1 is no top, value is the top number
int que_size;
map<int,int>M; void init(){
top_u = -;
que_size = ;
M.clear();
} int find_u_id(int u){
int u_id = -;
for(int i = ;i < que_size;i ++){
if(node[i].value == u){
u_id = i;
break;
}
}
return u_id;
} void Rotate(int x){
if(que_size < x){
OUT_OF_RANGE;
}else{
Node tmp = node[x - ];
for(int i = x - ;i >= ;i --){
node[i + ] = node[i];
}
node[] = tmp;
SUCCESS;
}
} void Prior(){
if(que_size == ){
EMPTY;
}else{
int max_value = -, max_value_id = -;
for(int i = ;i < que_size;i ++){
if(node[i].value > max_value){
max_value = node[i].value;
max_value_id = i;
}
}
Rotate(max_value_id + );
}
} void Choose(int u){
if(M[u] == ){
INVALID;
}else{
int u_id = find_u_id(u);
Rotate(u_id + );
}
} void Top(int u){
if(M[u] == ){
INVALID;
}else{
top_u = u;
SUCCESS;
}
} void Untop(){
if(top_u == -){
NO_SUCH_PERSON;
}else{
top_u = -;
SUCCESS;
}
} void Add(int u){
if(M[u] == ){
SAME;
}else{
M[u] = ;
node[que_size ++].set(u);
SUCCESS;
}
} void Close(int u){
if(M[u] == ){
INVALID;
}else{
M[u] = ;
int u_id = find_u_id(u);
if(u == top_u) top_u = -;
printf("close %d with %I64d.\n", u, node[u_id].word_num);
for(int i = u_id;i < que_size;i ++){
node[i] = node[i+];
}
que_size --;
}
} void Chat(int w){
if(que_size == ){
EMPTY;
}else{
if(top_u != -){
node[find_u_id(top_u)].word_num += w;
}else{
node[].word_num += w;
}
SUCCESS;
}
} void Bye(){
if(que_size == ) return ;
int top_id = -;
if(top_u != -){
top_id = find_u_id(top_u);
if(top_id != - && node[top_id].word_num != ){
printf("Bye %d: %I64d\n",node[top_id].value, node[top_id].word_num);
}
}
for(int i = ;i < que_size;i ++){
if(i == top_id) continue;
if(node[i].word_num == ) continue;
printf("Bye %d: %I64d\n",node[i].value, node[i].word_num);
}
} int main(){
int T, n;
char command[];
scanf("%d",&T);
while(T --){
scanf("%d\n",&n);
init();
for(int i = ;i <= n;i ++){
scanf("%s",command);
printf("Operation #%d: ",i);
if( == strcmp("Prior",command)){
Prior();
}else if( == strcmp("Untop",command)){
Untop();
}else {
int u;
scanf("%d",&u);
if( == strcmp("Add",command)){
Add(u);
}else if( == strcmp("Close",command)){
Close(u);
}else if( == strcmp("Chat",command)){
Chat(u);
}else if( == strcmp("Rotate",command)){
Rotate(u);
}else if( == strcmp("Choose",command)){
Choose(u);
}else if( == strcmp("Top",command)){
Top(u);
}
}
}
Bye();
}
return ;
}