HDU 5071 Chat：數組模擬實現聊天窗口管理

題目大意

同 207405：模擬聊天窗口隊列，支持 Add/Close/Chat/Rotate/Prior/Choose/Top/Untop 8 種操作，最終按規則道別。

數據結構差異

本實現使用數組模擬隊列，而非鏈表：

• g[i] 存儲第 i 個窗口：prior (優先級), word (聊天字數)
• tot = 當前窗口數
• alwaysontop = always on top 窗口優先級 (-1 表示無)
• 數組順序即隊列順序，移動操作用 swap 實現

操作實現要點

Add u

掃描 g[0..tot-1] 查重，無重複則 g[tot++] = {u, 0}

Close u

查找優先級 u 的下標，輸出字數，後續元素前移覆蓋，tot--。若為 alwaysontop 則清除。

Chat w

alwaysontop 存在則找到其下標加 w，否則加給 g[0]。隊列空輸出 empty。

Rotate x

x 越界檢查。將 g[x-1] 逐步 swap 到 g[0]。

Prior

掃描找最大優先級下標，swap 到隊首。

Choose u

查找優先級 u，swap 到隊首。

Top u

查找優先級 u 存在則 alwaysontop = u。

Untop

alwaysontop 存在則清除。

道別邏輯

先檢查 alwaysontop 窗口（若有字數輸出），再遍歷隊列輸出其他有字數的窗口（跳過 alwaysontop）。

完整代碼

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
#define M 5010

struct Girl { int prior; LL word; } g[M];

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int tot = 0, alwaysontop = -1;
        for (int i = 1; i <= n; i++) {
            printf("Operation #%d: ", i);
            char op[20]; scanf("%s", op);
            if (strcmp(op, "Add") == 0) {
                int u; scanf("%d", &u);
                bool ok = true;
                for (int j = 0; j < tot; j++) if (g[j].prior == u) { ok = false; break; }
                if (ok) { g[tot++] = {u, 0}; puts("success."); }
                else puts("same priority.");
            } else if (strcmp(op, "Close") == 0) {
                int u; scanf("%d", &u);
                int pos = -1;
                for (int j = 0; j < tot; j++) if (g[j].prior == u) { pos = j; break; }
                if (pos == -1) puts("invalid priority.");
                else {
                    if (g[pos].prior == alwaysontop) alwaysontop = -1;
                    printf("close %d with %lld.\n", g[pos].prior, g[pos].word);
                    for (int j = pos; j < tot-1; j++) g[j] = g[j+1];
                    tot--;
                }
            } else if (strcmp(op, "Chat") == 0) {
                int w; scanf("%d", &w);
                if (tot == 0) puts("empty.");
                else {
                    int idx = 0;
                    if (alwaysontop != -1) 
                        for (int j = 0; j < tot; j++) if (g[j].prior == alwaysontop) { idx = j; break; }
                    g[idx].word += w;
                    puts("success.");
                }
            } else if (strcmp(op, "Rotate") == 0) {
                int x; scanf("%d", &x);
                if (x < 1 || x > tot) puts("out of range.");
                else { for (int j = x-1; j > 0; j--) swap(g[j], g[j-1]); puts("success."); }
            } else if (strcmp(op, "Prior") == 0) {
                if (tot == 0) puts("empty.");
                else { int idx = 0; for (int j = 1; j < tot; j++) if (g[j].prior > g[idx].prior) idx = j; for (int j = idx; j > 0; j--) swap(g[j], g[j-1]); puts("success."); }
            } else if (strcmp(op, "Choose") == 0) {
                int u; scanf("%d", &u);
                int pos = -1;
                for (int j = 0; j < tot; j++) if (g[j].prior == u) { pos = j; break; }
                if (pos == -1) puts("invalid priority.");
                else { for (int j = pos; j > 0; j--) swap(g[j], g[j-1]); puts("success."); }
            } else if (strcmp(op, "Top") == 0) {
                int u; scanf("%d", &u);
                bool ok = false;
                for (int j = 0; j < tot; j++) if (g[j].prior == u) { ok = true; break; }
                if (ok) { alwaysontop = u; puts("success."); }
                else puts("invalid priority.");
            } else if (strcmp(op, "Untop") == 0) {
                if (alwaysontop == -1) puts("no such person.");
                else { alwaysontop = -1; puts("success."); }
            }
        }
        // 道別
        if (alwaysontop != -1) {
            for (int j = 0; j < tot; j++) if (g[j].prior == alwaysontop && g[j].word)
                printf("Bye %d: %lld\n", g[j].prior, g[j].word);
        }
        for (int j = 0; j < tot; j++) 
            if (g[j].word && g[j].prior != alwaysontop)
                printf("Bye %d: %lld\n", g[j].prior, g[j].word);
    }
    return 0;
}

複雜度分析

n ≤ 5000，每次操作 O(n) 掃描/移動，總時間 O(n²) = 2.5×10⁷，完全可行。數組實現比鏈表代碼更簡潔。