মান লিখুন: আমাদের কাছে N উপাদান বিশিষ্ট একটি অ্যারে A রয়েছে। প্রতিটি অপারেশনে একটি উপাদান বেছে নিয়ে ১ বাড়ানো বা কমানো যায়। নিচের শর্তগুলো পূরণ করার জন্য ন্যূনতম কত অপারেশন দরকার তা বের করতে হবে:
- প্রতিটি i (1 থেকে n) এর জন্য, ১ম থেকে i-তম পদ পর্যন্ত যোগফল ০ নয়
- প্রতিটি i (1 থেকে n-1) এর জন্য, ১ম থেকে i-তম পদ পর্যন্ত যোগফলের চিহ্ন, ১ম থেকে (i+1)-তম পদ পর্যন্ত যোগফলের চিহ্ন থেকে ভিন্ন
উদাহরণ
যদি ইনপুট হয় A = [1, -3, 1, 0], তবে আউটপুট হবে 4, কারণ ১, -২, ২, -২ এভাবে রূপান্তর করতে ৪ অপারেশন লাগে। প্রিফিক্স সমগুলো ১, -১, ১, -১।
সমাধানের ধাপসমূহ
n := A এর আকার
ret := 0, sum := 0
for each ai in A:
nsum := sum + ai
যদি s > 0:
যদি nsum <= 0:
ret := ret + |nsum| + 1
ai := ai + |nsum| + 1
অন্যথায়:
যদি nsum >= 0:
ret := ret + nsum + 1
ai := ai - (nsum + 1)
sum := sum + ai
s := s * -1
ret রিটার্ন করুন
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
int util(vector<int> A, int s) {
int n = A.size();
int ret = 0;
int sum = 0;
for (int ai : A) {
int nsum = sum + ai;
if (s > 0) {
if (nsum <= 0) {
ret += abs(nsum) + 1;
ai = ai + abs(nsum) + 1;
}
} else {
if (nsum >= 0) {
ret += nsum + 1;
ai = ai - (nsum + 1);
}
}
sum += ai;
s *= -1;
}
return ret;
}
int solve(vector<int> A) {
int res = min(util(A, 1), util(A, -1));
return res;
}
int main() {
vector<int> A = { 1, -3, 1, 0 };
cout << solve(A) << endl;
}
ইনপুট
{ 1, -3, 1, 0 }
আউটপুট
4
