ধরুন আমাদের কাছে N উপাদান সহ একটি অ্যারে রয়েছে। প্রতিটি ক্রিয়াকলাপে, আমরা একটি উপাদান বাছাই এবং এটিকে 1 দ্বারা বৃদ্ধি বা হ্রাস করি। নিম্নলিখিত শর্তগুলি পূরণ করার জন্য আমাদের কমপক্ষে কতগুলি অপারেশন প্রয়োজন তা খুঁজে বের করতে হবে -
-
1 থেকে n রেঞ্জের প্রতিটি i এর জন্য, 1ম থেকে ith টার্ম পর্যন্ত পদের যোগফল 0 নয়
-
1 থেকে n - 1 পরিসরের প্রতিটি i-এর জন্য, 1ম থেকে ith পদের পদের চিহ্নটি 1ম থেকে (i+1)তম পদের পদের যোগফলের চিহ্ন থেকে আলাদা৷
সুতরাং, যদি ইনপুটটি A =[1, -3, 1, 0] এর মতো হয়, তবে আউটপুট হবে 4, কারণ আমরা 1, -2, 2, -2 এর মতো ক্রমটিকে চারটি অপারেশন দ্বারা রূপান্তর করতে পারি। প্রথম এক, দুই, তিন এবং চারটি পদের যোগফল হল 1, -1, 1 এবং -1৷
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
n := size of A ret := 0 sum := 0 for each ai in A, do nsum := sum + ai if s > 0, then: if nsum <= 0, then: ret := ret + |nsum| ai := ai + |nsum| Otherwise if nsum >= 0, then: ret := ret + nsum + 1 ai := ai - (nsum + 1) sum := sum + ai s := s * -1 return ret
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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