সি++-এ সুপার ওয়াশিং মেশিন

মান লিইয়ে নিই nটি সুপার ওয়াশিং মেশিন একটি সারিয়ে রয়েছে। প্রাথমিকভাবে, প্রতিটি ওয়াশিং মেশিনে কিছু ড্রেস রয়েছে বা খালি। এখন, প্রতিটি মুভে, আমরা যেকোনো m (1 ≤ m ≤ n) ওয়াশিং মেশিন বেছে নিতে পারি, এবং প্রতিটি ওয়াশিং মেশিন থেকে একটি ড্রেস এর সংলগ্ন ওয়াশিং মেশিনে একসাথে পাস করতে পারি। ধরুন একটি ইন্টিজার অ্যারে রয়েছে যা বাম থেকে ডান পর্যন্ত সারিয়ে প্রতিটি ওয়াশিং মেশিনে ড্রেসের সংখ্যা রিপ্রেজেন্ট করে, আমাদের সব ওয়াশিং মেশিনে একই সংখ্যক কাপড় করার জন্য ন্যূনতম মুভের সংখ্যা বের করতে হবে। যদি এটি করা সম্ভব না হয়, তবে -1 ফেরত দিন।

সুতরাং যখন ইনপুট হয় [1,0,5], তবে আউটপুট হবে ৩, কারণ 5 কে 0-এ পাঠাতে হবে, তখন বন্টন হবে [1, 1, 4], তারপর মাঝের 1 কে বামে, 4 কে 1-এ, তখন হবে [2,1,3], তারপর 2 কে 1-এ, সেটা চূড়ান্ত হবে [2,2,2]

समाधान पद्धति

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• sum := v-এর সব উপাদানের যোগফল
• n := v-এর আকার
• যদি sum mod n, 0-এর সমান নয়, তবে:
  • -1 ফেরত দিন
• req := sum / n, ret := 0, extra := 0
• i := 0 থেকে आरंभ করুন, जब i < n, আপডেট করুন (i 1 বাড়ান), করুন:
  • x := v[i]
  • extra := extra + (x - req)
  • ret := {ret, x - req, |extra|}-এর সর্বোচ্চ
• ret ফেরত দিন

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#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