মনে করুন, nটি সুপার ওয়াশিং মেশিন একটি সারিতে রয়েছে। প্রতিটি মেশিনে কিছু ড্রেস আছে বা খালি। প্রতিটি চলে আমরা যেকোনো m (1 ≤ m ≤ n) মেশিন বেছে নিয়ে প্রতিটির একটি ড্রেস তার পাশের মেশিনে একসাথে পাস করতে পারি। প্রতিটি মেশিনের ড্রেস সংখ্যা দেওয়া থাকলে, সব মেশিনে সমান সংখ্যক ড্রেস করতে ন্যূনতম চলে সংখ্যা বের করতে হবে। অসম্ভব হলে -1 রিটার্ন করুন।
ইনপুট [1,0,5] হলে, আউটপুট ৩। কারণ: ৫ থেকে ০-এ পাস -> [1,1,4], মধ্যটি বামে -> [2,1,3], ডানটি বামে -> [2,2,2]।
সমাধানের ধাপসমূহ
- sum := সব উপাদানের যোগফল, n := v.size()
- যদি sum % n != 0 হয়, -1 রিটার্ন
- req := sum / n, ret := 0, extra := 0
- i := 0 থেকে n-1 পর্যন্ত:
- x := v[i]
- extra += (x - req)
- ret = max(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
