मान लीजिए हमारे पास n तत्वों वाली एक सरणी A है, तत्व -1 से 1 की रेंज में हैं। और m क्वेरीज़ के लिए जोड़ियों की एक और सरणी Q है जैसे Q[i] = (li, ri)। क्वेरी का उत्तर 1 होगा जब सरणी a के तत्वों को इस तरह पुनर्व्यवस्थित किया जा सकता है कि योग Q[li] + ... + Q[ri] = 0, अन्यथा 0। हमें सभी क्वेरीज़ के उत्तर ढूंढने हैं।
इसलिए, यदि इनपुट A = [-1, 1, 1, 1, -1]; Q = [[1, 1], [2, 3], [3, 5], [2, 5], [1, 5]] है, तो आउटपुट [0, 1, 0, 1, 0] होगा।
चरण
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
n := size of A m := size of Q z := 0 for initialize , i := 0, when i < n, update (increase i by 1), do: z := z + (1 if a < 0, otherwise 0) if z > n - z, then: z := n - z for initialize i := 0, when i < m, update (increase i by 1), do: l := Q[i, 0] r := Q[i, 1] print 1 if (((r - l) mod 2 is 1 and (r - l + 1) / 2) <= z), otherwise 0
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void solve(vector<int> A, vector<vector<int>> Q){ int n = A.size(); int m = Q.size(); int z = 0; for (int a, i = 0; i < n; ++i) z += a < 0; if (z > n - z) z = n - z; for (int i = 0; i < m; i++){ int l = Q[i][0]; int r = Q[i][1]; cout << (((r - l) % 2 && (r - l + 1) / 2) <= z) << ", "; } } int main(){ vector<int> A = { -1, 1, 1, 1, -1 }; vector<vector<int>> Q = { { 1, 1 }, { 2, 3 }, { 3, 5 }, { 2, 5 }, { 1, 5 } }; solve(A, Q); }इनपुट
{ -1, 1, 1, 1, -1 }, { { 1, 1 }, { 2, 3 }, { 3, 5 }, { 2, 5 }, { 1, 5 } }आउटपुट
1, 0, 1, 0, 1,
