C++ में सुपर वॉशिंग मशीन्स समस्या

मान लीजिए हमारे पास एक पंक्ति में n सुपर वॉशिंग मशीनें हैं। प्रारंभ में, प्रत्येक वॉशिंग मशीन में कुछ कपड़े हैं या खाली है। अब, प्रत्येक चाल में, हम कोई भी m (1 ≤ m ≤ n) वॉशिंग मशीनें चुन सकते हैं, और प्रत्येक वॉशिंग मशीन का एक कपड़ा उसके आसन्न वॉशिंग मशीनों में से एक को एक साथ पास कर सकते हैं। मान लीजिए हमारे पास एक इंटीजर ऐरे है जो बाएं से दाएं पंक्ति में प्रत्येक वॉशिंग मशीन में कपड़ों की संख्या दर्शाता है, हमें सभी वॉशिंग मशीनों में समान संख्या में कपड़े बनाने के लिए न्यूनतम चालों की संख्या ढूंढनी है। यदि यह संभव नहीं है, तो -1 लौटाएं।

उदाहरण के लिए, जब इनपुट [1,0,5] है, तो आउटपुट 3 होगा: 5 से 0 को भेजें → [1,1,4], फिर मध्य से बाएं → [2,1,3], फिर 2 से 1 → [2,2,2]

समाधान दृष्टिकोण

1. sum := v के सभी तत्वों का योग।
2. n := v.size()।
3. यदि sum % n != 0, तो -1 लौटाएं (संभव नहीं)।
4. req := sum / n (प्रति मशीन आवश्यक कपड़े), ret := 0, extra := 0।
5. i = 0 से n-1 तक लूप करें:
   • x := v[i]
   • extra += (x - req)
   • ret = max({ret, x - req, |extra|})
6. ret लौटाएं।

अंतर्ज्ञान: ret किसी भी बिंदु पर आवश्यक अधिकतम असंतुलन को ट्रैक करता है: या तो एक मशीन का व्यक्तिगत अधिशेष/घाटा (x - req) या संचयी प्रवाह असंतुलन (|extra|)।

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 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;
    }
};

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

इनपुट

{2,1,6}

आउटपुट

3