Ежедневный бит (е) C ++ # 79, Общая проблема на собеседовании: максимальное количество книг, которые нужно взять
Сегодня мы рассмотрим распространенную проблему собеседования по C++: максимальное количество книг, которые нужно взять.
Учитывая массив, описывающий количество книг на книжных полках, определите максимальное количество книг, которое вы можете взять при следующих условиях:
- вы должны брать книги с соседних книжных полок
- количество книг, которые вы берете с каждой книжной полки, должно строго возрастать
Например, для ввода {8, 5, 2, 7, 9} мы можем взять одну книгу с первой полки (с нулевым индексом), две с второй полки, семь с третьей полки и, наконец, девять книг с четвертой полки. всего 19.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/ax53xfKTa.
Решение
Первое наблюдение, которое нам необходимо сделать, заключается в том, что максимальное количество книг, которое мы можем взять, если игнорировать количество книг на предыдущих полках, представляет собой просто ряд 1 + 2 + 3 + … + n, который в сумме дает n*(n+ 1)/2.
Мы можем не достичь этого оптимального числа, потому что у нас либо закончатся книжные полки, либо мы столкнемся с книжной полкой с меньшим количеством книг, чем мы хотели бы взять; назовем эти узкие места.
Однако здесь есть хорошая недвижимость. Если мы знаем, сколько книг (в лучшем случае) мы могли бы взять, если бы у нас было узкое место, мы можем вычислить результат для книжной полки как n+(n-1)… до (но не включая) узкого места плюс количество книги, которые мы можем взять, заканчивающиеся в узком месте.
Чтобы собрать это вместе, нам нужно отслеживать две части информации:
- текущие узкие места
- количество книг, которые мы можем взять, оканчивающихся на каждом индексе
#include <vector> long long count_books(long long start, long long cnt) { // A full series of 1+2+3... is n*(n+1)/2 // However, we only want the top cnt elements. auto sum = [](long long n) -> long long { if (n <= 0) return 0; return n*(n+1)/2; }; return sum(start)-sum(start-cnt); } size_t maximum_books(const std::vector<size_t>& shelves) { std::vector<size_t> dp(shelves.size(),0); std::vector<size_t> bottleneck; size_t max = 0; for (size_t i = 0; i < shelves.size(); ++i) { // If the current shelf has less (or equal) books than the // previous bottleneck plus the distance, then the current // shelf is more of a bottleneck. while(!bottleneck.empty() && shelves[i] <= shelves[bottleneck.back()] + (i - bottleneck.back())) bottleneck.pop_back(); // The number of books we can take: if (!bottleneck.empty()) { // The number of books for the last bottleneck. dp[i] += dp[bottleneck.back()]; // Plus shelves[i] + shelves[i-1]... but only until // we reach the last bottleneck. dp[i] += count_books(shelves[i], i - bottleneck.back()); } else { // If there is no bottleneck, the end is the start // of the array. dp[i] += count_books(shelves[i], i + 1); } // This shelf is now the potential new bottleneck. bottleneck.push_back(i); max = std::max(max,dp[i]); } return max; }
Нажмите, чтобы открыть решение в Compiler Explorer.