Super Washing Machines: เครื่องซักผ้าซูเปอร์ใน C++

ปัญหา

มีเครื่องซักผ้า n เครื่องเรียงแถว แต่ละเครื่องมีชุดผ้า v[i] ชุด ทุกรอบเลือกเครื่องใดก็ได้ m เครื่อง (1 ≤ m ≤ n) ส่งผ้า 1 ชุดไปเครื่องข้างเคียง (ซ้าย/ขวา) พร้อมกัน หา จำนวนรอบน้อยที่สุด ให้ทุกเครื่องมีผ้าเท่ากัน ไม่ได้คืน -1

ตัวอย่าง: [1,0,5] → 3 รอบ

ข้อสังเกตสำคัญ

1. ผลรวมต้องหาร n ลงตัว ไม่งั้น Impossible → -1
2. เป้าหมายแต่ละเครื่อง = avg = sum/n
3. พิจารณา Net Flow ผ่านขอบระหว่างเครื่อง i และ i+1

Greedy Insight

ที่ตำแหน่ง i จำนวนผ้าที่ต้อง "ไหลผ่าน" ขอบทางขวา = prefix_sum[i] - (i+1)*avg

จำนวนรอบขั้นต่ำ = max ของ 3 ค่า:

• v[i] - avg (ผ้าที่เครื่อง i ต้องส่งออก ถ้ามากกว่า avg)
• |prefix_sum[i] - (i+1)*avg| (Net flow ผ่านขอบ i)
• ค่าสูงสุดที่เคยเจอ

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMinMoves(vector<int>& v) {
        int sum = accumulate(v.begin(), v.end(), 0);
        int n = v.size();
        if (sum % n != 0) return -1;
        
        int avg = sum / n;
        int ret = 0;
        int extra = 0;  // Net flow ผ่านขอบปัจจุบัน
        
        for (int i = 0; i < n; i++) {
            int diff = v[i] - avg;
            extra += diff;  // Net flow สะสม
            // จำนวนรอบ = max( ผ้าที่เครื่องนี้ส่งออก, net flow ผ่านขอบ, ค่าสูงสุดก่อนหน้า )
            ret = max({ret, diff, abs(extra)});
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 1, 6};
    cout << ob.findMinMoves(v);  // 3
    return 0;
}

การเดินตัวอย่าง [2,1,6], avg=3

ความซับซ้อน

• Time: O(n)
• Space: O(1)

Input / Output

Input:  {2,1,6}
Output: 3