Initial commit

1 files changed, 46 insertions, 0 deletions

diff --git a/02_sorting_and_searching/collecting_numbers_2216.cpp b/02_sorting_and_searching/collecting_numbers_2216.cpp
new file mode 100644
index 0000000..1adcf28
--- /dev/null
+++ b/02_sorting_and_searching/collecting_numbers_2216.cpp
@@ -0,0 +1,46 @@
+#include <iostream>
+#include <vector>
+
+int main() {
+        size_t n, x, s{1}, l{0};
+        std::cin >> n;
+        std::vector<size_t> b(n);
+        for (size_t i = 0; i < n; i++) {
+                std::cin >> x;
+                b[x-1] = i;
+        }
+        for (size_t i = 0; i < n; i++) {
+                s += b[i] < l;
+                l = b[i];
+        }
+        std::cout << s << "\n";
+}
+
+
+// The code below solves a different problem: it finds the minimum number
+// of ascending chains needed to partition the given list of numbers.
+
+#if 0
+
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+        size_t n;
+        std::vector<size_t> s;
+        std::cin >> n;
+        for (size_t i = 0; i < n; i++) {
+                size_t x;
+                std::cin >> x;
+                auto it = std::lower_bound(
+                    s.begin(), s.end(), x, std::greater<size_t>());
+                if (it != s.end())
+                        *it = x;
+                else
+                        s.push_back(x);
+        }
+        std::cout << s.size() << std::endl;
+}
+
+#endif