Ежедневный бит (е) 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.