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