मान लीजिए हमारे पास N तत्वों वाला एक ऐरे A है। प्रत्येक ऑपरेशन में, हम एक तत्व चुनते हैं और इसे 1 से बढ़ाते या घटाते हैं। हमें निम्नलिखित शर्तों को पूरा करने के लिए आवश्यक न्यूनतम ऑपरेशनों की संख्या ढूंढनी है:
- रेंज 1 से n में प्रत्येक i के लिए, 1वें से iवें पद तक के पदों का योग 0 नहीं है
- रेंज 1 से n - 1 में प्रत्येक i के लिए, 1वें से iवें पद तक के पदों का चिह्न, 1वें से (i+1)वें पद तक के पदों के योग के चिह्न से अलग है।
उदाहरण के लिए, यदि इनपुट A = [1, -3, 1, 0] है, तो आउटपुट 4 होगा, क्योंकि हम अनुक्रम को 1, -2, 2, -2 में चार ऑपरेशनों द्वारा बदल सकते हैं। पहले एक, दो, तीन और चार पदों के योग 1, -1, 1 और -1 हैं।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := A का आकार ret := 0 sum := 0 A के प्रत्येक ai के लिए, करें nsum := sum + ai यदि s > 0, तो: यदि nsum <= 0, तो: ret := ret + |nsum| ai := ai + |nsum| अन्यथा यदि nsum >= 0, तो: ret := ret + nsum + 1 ai := ai - (nsum + 1) sum := sum + ai s := s * -1 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
