ภาพรวมปัญหา
มีเครื่องซักผ้า n เครื่องเรียงติดกัน แต่ละเครื่องมีชุดผ้าบางจำนวน ในแต่ละขั้นตอน เลือก m เครื่อง (1≤m≤n) ส่งผ้า 1 ชุดจากแต่ละเครื่องไปเครื่องข้างเคียง (ซ้ายหรือขวา) พร้อมกัน หาขั้นตอนน้อยที่สุดทำให้ทุกเครื่องมีผ้าเท่ากัน ไม่ได้คืน -1
ตัวอย่าง
[1,0,5] → 3 ขั้นตอน: 5→0 ได้ [1,1,4], แล้วกลาง→ซ้าย, ขวา→กลาง ได้ [2,1,3], แล้วซ้าย→กลาง ได้ [2,2,2]
แนวทางแก้ปัญหา (Greedy / Prefix Sum)
- sum = ผลรวมทั้งหมด, n = จำนวนเครื่อง
- ถ้า sum % n != 0 → -1 (หารไม่ลง)
- req = sum / n (เป้าหมายแต่ละเครื่อง)
- extra = ผลรวมสะสมของ (v[i] - req) จากซ้ายไปขวา
- คำตอบ = max( v[i] - req, |extra| ) ทุก i
- เหตุผล: v[i]-req = ผ้าที่เครื่อง i ต้องส่งออก, |extra| = ผ้าที่ต้องข้ามช่องว่าง i→i+1
ตัวอย่างโปรแกรม
#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 req = sum / n;
int ret = 0, extra = 0;
for(int i = 0; i < n; i++) {
int x = v[i];
extra += (x - req);
ret = max({ret, x - req, abs(extra)});
}
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {2, 1, 6};
cout << (ob.findMinMoves(v));
}
Input
{2,1,6}
Output
3
