मान लीजिए हमारे पास n तत्वों वाली एक सरणी A है और एक और संख्या s है। टेबल पर एक खाली पानी का मग और n गैर-खाली पानी के मग हैं। एक खेल में, कुछ खिलाड़ी हैं। प्रत्येक चाल में, एक खिलाड़ी पानी के एक गैर-खाली मग को लेता है और उससे सारा पानी कप में डालता है। यदि यह ओवरफ्लो होता है, तो खिलाड़ी हार जाएगा। हमें जांचना है कि क्या उन सभी का विजेता होगा या नहीं (कप ओवरफ्लो नहीं होगा)। यदि एक कप पहले से पूरी तरह भरा हुआ है, तो अगला खिलाड़ी अपनी चाल नहीं खेलेगा। यहां s खाली कप की क्षमता है और A[i] i-वें कप में मौजूद पानी की मात्रा है।
इसलिए, यदि इनपुट A = [3, 1, 3]; s = 4 है, तो आउटपुट True होगा, क्योंकि पहले और दूसरे खिलाड़ी द्वारा कप भर जाएगा। अंतिम के लिए, खिलाड़ी वह चाल नहीं खेलेगा।
चरण
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
k := 0 n := size of A sort the array A for initialize i := 0, when i < n - 1, update (increase i by 1), do: k := k + A[i] if k > s, then: return false Otherwise return true
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; bool solve(vector<int> A, int s){ int k = 0; int n = A.size(); sort(A.begin(), A.end()); for (int i = 0; i < n - 1; i++) k += A[i]; if (k > s) return false; else return true; } int main(){ vector<int> A = { 3, 1, 3 }; int s = 4; cout << solve(A, s) << endl; }इनपुट
{ 3, 1, 3 }, 4आउटपुट
1