C語言OJ題目：水牛排隊問題的優化解法分析

這是一道經典的OJ（Online Judge）算法題目：農夫約翰有N頭牛（1 ≤ N ≤ 1000），每頭牛有品種編碼。通過移除某一品種的所有牛，使剩餘序列中同品種連續牛的數量最大化。本文分析常規思路並探討優化方案。

問題描述

輸入：牛的總數N，及N個品種編碼B[i]（0 ≤ B[i] ≤ 1,000,000）
輸出：移除某一品種後，最大連續同品種牛的數量

樣例分析

輸入：9頭牛，品種序列：2, 7, 3, 7, 7, 3, 7, 5, 7
移除品種3後：2, 7, 7, 7, 7, 5, 7 → 最大連續4頭品種7的牛
其他移除方案最大僅得2頭，故答案為4

常規解法（暴力枚舉）

1. 統計所有不同品種（去重）
2. 對每個品種，模擬移除後掃描數組計算最大連續長度
3. 取所有品種移除方案中的最大值

時間複雜度：O(K × N)，K為品種數，最壞情況K=N，即O(N²)。對於N≤1000可通過。

優化思路

單次遍歷法

維護每個品種的：當前連續長度、最大連續長度、上一次出現位置。一次遍歷中動態更新，但需處理「移除某品種」的邏輯，實現較複雜。

分組+雙指針

將數組按品種分組記錄位置，對每個目標品種，利用雙指針在其位置列表中尋找最大間隔，間隔內不含其他目標品種。需配合前綴和或線段樹查詢區間內不同品種數。

代碼框架（常規解法）

#include <stdio.h>
#define MAXN 1005

int main() {
    int N, B[MAXN];
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d", &B[i]);

    // 獲取所有品種
    int breeds[MAXN], breedCnt = 0;
    for (int i = 0; i < N; i++) {
        int found = 0;
        for (int j = 0; j < breedCnt; j++)
            if (breeds[j] == B[i]) { found = 1; break; }
        if (!found) breeds[breedCnt++] = B[i];
    }

    int ans = 0;
    // 枚舉移除的品種
    for (int b = 0; b < breedCnt; b++) {
        int cur = 0, maxLen = 0;
        for (int i = 0; i < N; i++) {
            if (B[i] == breeds[b]) { cur = 0; continue; }
            cur++;
            if (cur > maxLen) maxLen = cur;
        }
        if (maxLen > ans) ans = maxLen;
    }
    printf("%d\n", ans);
    return 0;
}

總結

對於N≤1000的數據範圍，常規O(N²)解法完全足夠。若N擴大到10⁵級別，需引入更高級數據結構（如線段樹、莫隊算法）優化至O(N log N)或O(N√N)。理解問題本質、選擇合適複雜度的算法是關鍵。