HDU 5071 Chat【模拟】【vector】

发表于 | 更新于 | 分类于

题目大意：

现在有一个聊天界面(可以想象为一个队列)，请你模拟以下操作：

  1. Add u： 在队列中加入一个优先级为u的窗口。如果已经存在同优先级的窗口，输出”same priority.”，否则输出 “success.”。
  2. Close u：将队列中优先级为u的窗口关闭。如果不存在优先级为u的窗口，输出”invalid priority.” 否则输出”close u with c.”，其中c是和优先级为u的窗口的聊天次数。
  3. Chat w：向当前在最顶端的窗口输入w句话。如果当前队列中没有窗口，输出”empty.” 否则输出”success.”。
  4. Rotate x：将当前排在第x位的窗口翻转到最前面。如果x非法，输出”out of range.” 否则输出”success.”。
  5. Prior：将优先级最高的窗口翻转到最前面。如果当前队列中没有窗口，输出”empty.” 否则输出”success.”。
  6. Choose u：将优先级为u的窗口翻转到最前面。如果当前队列中没有此窗口，输出”invalid priority.” 否则输出”success.”。
  7. Top u：将优先级为u的窗口置顶。如果当前队列中没有此窗口，输出”invalid priority.” 否则输出”success.”。
  8. Untop：取消当前置顶的窗口。如果当前没有置顶的窗口，输出”no such person.” 否则输出 “success.”。

解题思路：

我们可以用vector来模拟这个“队列”，里面的元素为记录优先级&聊天次数的pair对，然后直接做就好了(可以通过写一些函数来模块化一些操作来减少代码量)。

PS：对于置顶这个操作，可以直接用一个变量来记录优先级，通过优先级找到它在队列中的原始位置，因为这个值是不变的，对于后续操作十分方便。

PPS：active时不要忘记忽略掉聊天次数为0的那些窗口。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

char op[9];
int t, n, x, mx, pos, val;
pair<int, long long> p;
vector<pair<int, long long> > V;

int Find(int v)
{
    for(int i = 0; i < V.size(); ++i)
        if(V[i].first == v)
            return i;
    return -1;
}

void Erase(int v)
{
    //删除第v个
    int idx = 0;
    for(auto it = V.begin(); it != V.end(); ++it, ++idx)
    {
        if(idx == v)
        {
            V.erase(it);
            return ;
        }
    }
}

void Add()
{
    scanf("%d", &x);
    pos = Find(x);
    if(pos != -1)
        puts("same priority.");
    else
    {
        V.push_back({x, 0});
        puts("success.");
    }
}

void Close()
{
    scanf("%d", &x);
    pos = Find(x);
    if(pos == -1)
        puts("invalid priority.");
    else
    {
        printf("close %d with %lld.\n", V[pos].first, V[pos].second);
        Erase(pos);
    }
}

void Chat()
{
    scanf("%d", &x);
    if(V.empty())
        puts("empty.");
    else
    {
        if(val)
            pos = Find(val);
        else
            pos = 0;
        V[pos].second += x;
        puts("success.");
    }
}

void Rotate(int x)
{
    --x;
    if(x < 0 || x >= V.size())
        puts("out of range.");
    else
    {
        p = V[x];
        Erase(x);
        V.insert(V.begin(), p);
        puts("success.");
    }
}

void Prior()
{
    if(V.empty())
        puts("empty.");
    else
    {
        mx = -1;
        for(int i = 0; i < V.size(); ++i)
        {
            if(V[i].first > mx)
            {
                mx = V[i].first;
                pos = i;
            }
        }
        Rotate(pos + 1);
    }
}

void Choose()
{
    scanf("%d", &x);
    pos = Find(x);
    if(pos == -1)
        puts("invalid priority.");
    else
        Rotate(pos + 1);
}

void Top()
{
    scanf("%d", &x);
    pos = Find(x);
    if(pos == -1)
        puts("invalid priority.");
    else
    {
        val = x;
        puts("success.");
    }
}

void Untop()
{
    if(val)
    {
        val = 0;
        puts("success.");
    }
    else
        puts("no such person.");
}

void active()
{
    if(val)
    {
        pos = Find(val);
        if(V[pos].second)
        {
            printf("Bye %d: %lld\n", V[pos].first, V[pos].second);
            Erase(pos);
        }
    }
    for(int i = 0; i < V.size(); ++i)
        if(V[i].second)
            printf("Bye %d: %lld\n", V[i].first, V[i].second);
}

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        val = 0;
        V.clear();
        scanf("%d", &n);
        for(int cas = 1; cas <= n; ++cas)
        {
            scanf("%s", op);
            printf("Operation #%d: ", cas);
            if(op[0] == 'A')
                Add();
            else if(op[0] == 'R')
                scanf("%d", &x), Rotate(x);
            else if(op[0] == 'P')
                Prior();
            else if(op[0] == 'T')
                Top();
            else if(op[0] == 'U')
                Untop();
            else if(op[1] == 'l')
                Close();
            else if(op[2] == 'a')
                Chat();
            else
                Choose();
        }
        active();
    }
    return 0;
}
Donate comment here
0%