สมมุติว่าเรามีเครื่องซักผ้าซุปเปอร์อยู่ติดกัน ในขั้นต้น เครื่องซักผ้าแต่ละเครื่องมีชุดหรือว่างเปล่า สำหรับการย้ายแต่ละครั้ง เราสามารถเลือกเครื่องซักผ้า m (1 ≤ m ≤ n) ใดๆ และส่งเสื้อผ้าหนึ่งชุดของเครื่องซักผ้าแต่ละเครื่องไปยังเครื่องซักผ้าเครื่องใดเครื่องหนึ่งที่อยู่ติดกันได้พร้อมกัน สมมติว่าเรามีอาร์เรย์จำนวนเต็มหนึ่งชุดที่แสดงจำนวนชุดในเครื่องซักผ้าแต่ละเครื่องจากซ้ายไปขวาในแถว เราควรหาจำนวนการเคลื่อนไหวขั้นต่ำเพื่อให้เครื่องซักผ้าทั้งหมดมีจำนวนเสื้อผ้าเท่ากัน หากทำไม่ได้ ให้คืนค่า -1
ดังนั้นเมื่ออินพุตเป็น [1,0,5] เอาต์พุตจะเป็น 3 เนื่องจากส่ง 5 ถึง 0 ดังนั้นการกระจายจะเป็น [1, 1, 4] จากนั้นกลาง 1 ไปทางซ้าย 1 ไปที่ 1 แล้วจะกลายเป็น [2,1,3] จากนั้นเป็น 2 ต่อ 1 ในที่สุดก็เป็น [2,2,2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- sum :=ผลรวมขององค์ประกอบทั้งหมดของ v
- n :=ขนาดของวี
- ถ้า sum mod n ไม่เท่ากับ 0 แล้ว −
- คืน -1
- req :=sum / n, ret :=0, extra :=0
- สำหรับการเริ่มต้น i :=0 เมื่อฉัน
- x :=v[i]
- พิเศษ :=พิเศษ + (x - req)
- ret :=สูงสุด {ret, x - req, |extra|
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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;
int 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;
}
};
main(){
Solution ob;
vector<int> v = {2,1,6};
cout << (ob.findMinMoves(v));
} อินพุต
{2,1,6} ผลลัพธ์
3
