POJ 3276 Face The Right Way：翻轉區間最小化操作數

問題大意

N 條牛排成一行，朝前(F)或朝後(B)。機器固定翻轉連續 K 條牛（1≤K≤N），每次操作反轉方向。求使所有牛朝前的最小 K 及對應最小操作數 M。

核心觀察

枚舉 K (1..N)，貪心從左到右：若當前牛實際朝向為 B（考慮前面翻轉次數奇偶性），則必須在這裡翻轉。用差分數組 f[i] 記錄是否在 i 處翻轉，sum 維護影響當前位置的翻轉次數。

檢查函數 calc(K)

int calc(int k) {
    memset(f,0,sizeof(f));
    int sum=0, res=0;
    for (int i=0; i+k<=N; i++) {
        if ((dir[i]+sum)%2 != 0) { res++; f[i]=1; }
        sum += f[i];
        if (i+1 >= k) sum -= f[i+1-k];
    }
    for (int i=N-k+1; i= k) sum -= f[i+1-k];
    }
    return res;
}

主程序

枚舉 K，記錄最小操作數及對應最小 K。輸出 K 和 M。

複雜度

O(N²)，N≤5000，約 2.5×10⁷ 操作，通過。