C++ Решение интересной задачки с РОИ-2017

Irval · 10 Ноя 2021

Задача: Сушка
Тётя Люба только что постирала всё белье - n вещей - и теперь перед ней стоит непростая задача - как его высушить за минимальное время. Сразу после стирки, i-я постиранная вещь имеет влажность ai. Если она сушится на веревке, то за минуту ее влажность уменьшается на 1, а если на батарее - то на k (если влажность была меньше k, то она становится равной 0).
Причем веревок у тёти Любы много (хватает для одновременной сушки всех вещей), а батарея только одна, причем такая маленькая, что на ней нельзя сушить две вещи одновременно. Тётя Люба может может каждую минуту выбрать ровно одну вещь и повесить ее сушиться на батарею. За какое минимальное время она сможет высушить все вещи?

Входные данные
Первая строка содержит число n (1 <= n <= 100000). Вторая строка содержит числа ai (1 <= ai <= 10e9). Третья строка содержит число k (1 <= k <= 1e9).

Выходные данные
Выведите одно число - минимальное число минут, за которые можно высушить все вещи.

Примеры

Ввод	Вывод
3 2 3 9 5	3
3 2 3 6 5	2

Файл с решением задачи на C++:

Пожалуйста, авторизуйтесь для просмотра ссылки.

.
Сложность алгоритма - O(66N + NlogN).
Идея алгоритма:

Основополагающим действием будет выбор элемента для вычитания из него K. Думаю, не нужно объяснять, почему самым оптимальным будет всегда использовать максимум, а после его изменения уже изменять его положение в массиве. Самым наивным решением был бы честный подсчет каждого элемента, но тогда сложность алгоритма уходит в N^2, что явно не будет заходить для n = 10^5. Предлагаю оставить идею тривиального решения и добавить несколько оптимизаций:
1) Отсортировать лучше Radix'ом, тогда сложность сортировки составит V*N.
2) У нас нет необходимости знать промежуточные значения каждого элемента. Достаточно помнить, что из каждого, кроме последнего, мы вычтем i единиц на i'м шаге. Остается только сделать проверку на a[k] == i, после мы будем удалять этот элемент из массива вещей mas.
С последним элементом немного сложнее. Чтобы облегчить свою жизнь, предлагаю считать, что из него мы тоже вычитали i-1 единиц до i-го этапа. Для 0го i это никак не повлияет, но потом для соблюдения условия необходимо прибавлять i к новому значению максимума (последнего элемента) и вставлять его в массив с помощью бинпоиска.

KlareoN · 10 Ноя 2021

Слишком умная задача для обладателей этого форума.

Жду решение задач по ЕГЭ информатики.

Irval · 10 Ноя 2021

KlareoN написал(а):
Слишком умная задача для обладателей этого форума.

Жду решение задач по ЕГЭ информатики.

В предверии экзаменов обязательно сделаю :)

bAnan_N0gi · 10 Ноя 2021

отправлю ка я, моему учителю эту задачку :roflanEbalo:

sn0wyQ · 11 Ноя 2021

1) Зачем самому писать реализацию upper_bound когда есть std::upper_bound?
2) qsort для 10^5 элементов отработает в пару раз быстрее radix sort. Плюс не надо лишний раз мучаться, сразу std::sort
И самое главное 3) vector::erase и vector::insert работают за O(N). Итого твоя асимптотика O(a_max*N), заходить не должно по TLю на нормальных тестах, так что РЕШЕНИЕ, вообще говоря, НЕПРАВИЛЬНОЕ. (Не зайдет например если у тебя 10^5 чисел по 10^9, a k = 2). Пруф почему асимптотика O(a_max*N): у тебя при k = 1 количество выполнений do {...} while(...); будет в точности равно максимальному элементу (a_max). Причем в худшем случае a_max*n = 10^9 * 10^5 = 10^14 - таска не зашла по TLю.

Правильное решение:
А я пока ХЗ, таска достаточно трудная... Завтра утром попробую что-нибудь придумать
UPD: Правильное решение - https://yougame.biz/threads/231893/#post-2433996

Irval · 11 Ноя 2021

sn0wyQ написал(а):
Правильное решение:

Я заливал это решение на немного изменённое задание в тест системах, в итоге TL не вылезал.

sn0wyQ · 11 Ноя 2021

Irval написал(а):
Я заливал это решение на немного изменённое задание в тест системах, в итоге TL не вылезал.

Значит или есть какие-то доп ограничения в измененном задании, или у жюри очень плохие тесты.

Я немного изменил твой код, чтобы вместо стандартного ввода он сразу получил себе на вход n = 10^5, a_i = 10^9, k = 1. Всего время выполнения, как и предсказывал, я так и не дождался. А потом просто поставил отсечение по времени на 5 секундах которое говорило что TL:

C++:

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;

void radixsort(long long a[], int n) {
  int count[10];
  long long* output = new long long[n];
  memset(output, 0, n * sizeof(*output));
  memset(count, 0, sizeof(count));
  long long max = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] > max) {
      max = a[i];
    }
  }
  int maxdigits = 0;
  while (max) {
    maxdigits++;
    max /= 10;
  }
  for (int j = 0; j < maxdigits; j++) {
    for (int i = 0; i < n; i++) {
      long long t = std::pow(10, j);
      count[(a[i] % (10 * t)) / t]++;
    }
    int k = 0;
    for (int p = 0; p < 10; p++) {
      for (int i = 0; i < n; i++) {
        long long t = std::pow(10, j);
        if ((a[i] % (10 * t)) / t == p) {
          output[k] = a[i];
          k++;
        }
      }
    }
    memset(count, 0, sizeof(count));
    for (int i = 0; i < n; ++i) {
      a[i] = output[i];
    }
  }
  delete[] output;
}

void print(vector<long long> a, int n) {
  for (int i = 0; i < n; ++i) {
    std::cout << a[i] << " ";
  }
  std::cout << std::endl;
}

template<class ForwardIt, class T>
ForwardIt ub(ForwardIt first, ForwardIt last, const T& value)
{
  ForwardIt it;
  typename std::iterator_traits<ForwardIt>::difference_type count, step;
  count = std::distance(first, last);

  while (count > 0) {
    it = first;
    step = count / 2;
    std::advance(it, step);
    if (!(value < *it)) {
      first = ++it;
      count -= step + 1;
    }
    else
      count = step;
  }
  return first;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  long long n, k;
  long long a[100000];
  //cin >> n;
  n = 100000;
  for (int i = 0; i < n; i++) {
    // long long tmp;
    // cin >> tmp;
    // a[i] = tmp;
    a[i] = 1e9;
  }
  //cin >> k;
  k = 1;

  clock_t start = clock();

  radixsort(a, n);
  vector<long long> mas;
  for (int i = 0; i < n; i++)
    mas.push_back(a[i]);

  long long ans = 0;

  do {
    if ((clock() - start > 5000)) {
      cout << "Elapsed time is over 5 seconds!\nVerdict: TL" << endl;
      return 0;
    }

    long long _min = mas[0] - ans;
    long long _max = mas[n - 1] - ans;
    if (_min <= 1 && n != 1) {
      int lastInd = 1;
      while (lastInd < n - 1 && mas[lastInd] <= ans + 1) lastInd++;
      mas.erase(mas.begin(), std::next(mas.begin(), lastInd));
      n -= lastInd;
    }
    ans++;

    if (mas.empty())
      break;
    mas.pop_back();

    if (_max > k) {
      _max -= k;
      _max += ans;
      mas.insert(ub(mas.begin(), mas.end(), _max), _max);
    }
    else n--;
  } while (!mas.empty());

  cout << "Time elapsed: " << (clock() - start) / 1000 << endl;
  cout << ans;
}

Результат:

Код:

C:\CPP\lazha\sushka\cmake-build-release\sushka.exe
Elapsed time is over 5 seconds!
Verdict: TL

Process finished with exit code 0

sn0wyQ · 11 Ноя 2021

Итак, правильное решение:
Будем бинарным поиском искать ответ. Пускай мы хотим проверить можем ли мы успеть за M минут. Тогда мы из каждого числа вычтем M (за каждую минуту как минимум на 1 влажность вещи уменьшается), плюс еще суммарно M раз мы можем вычесть из каких-то чисел дополнительно по K-1 - ведь за M минут суммарно M раз какие-то вещи висели на батарее. Тогда если мы хотим проверить хватит ли нам M минут, мы идем по всем числам в нашем массиве и, если какое-то a_i больше M, мы вычитаем из времени, которое вещи суммарно могут провисеть на батарее, (a_i - m) / (k - 1) округленное вверх - ровно столько раз текущей вещи надо было повисеть на батарее, чтобы через M минут она высушилась. Если оказывается, что сумма округленных вверх (a_i - m) / (k - 1) больше M, то за M минут все вещи высохнуть не успеют.
Значит мы можем бинарным поиском искать M, которое и будет ответом.
Итоговая асимптотика - O(NlogN) - мы O(logN) раз перебираем M тратя каждый раз на проверку O(N) операций

C++:

#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n, k, l = 0, r = 0;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    r = max(r, a[i]);
  }
  cin >> k;

  if (k == 1) {
    cout << r;
    return 0;
  }

  while (l < r - 1) {
    int m = (l + r) / 2;
    int left = m;
    for (int i = 0; i < n; i++) {
      if (a[i] > m) {
        left -= (a[i] - m + k - 2) / (k - 1);
      }
    }
    if (left < 0) {
      l = m + 1;
    } else {
      r = m;
    }
  }

  cout << l;
}

Irval · 11 Ноя 2021

sn0wyQ написал(а):
Итак, правильное решение:
Будем бинарным поиском искать ответ. Пускай мы хотим проверить можем ли мы успеть за M минут. Тогда мы из каждого числа вычтем M (за каждую минуту как минимум на 1 влажность вещи уменьшается), плюс еще суммарно M раз мы можем вычесть из каких-то чисел дополнительно по K-1 - ведь за M минут суммарно M раз какие-то вещи висели на батарее. Тогда если мы хотим проверить хватит ли нам M минут, мы идем по всем числам в нашем массиве и, если какое-то a_i больше M, мы вычитаем из времени, которое вещи суммарно могут провисеть на батарее, (a_i - m) / (k - 1) округленное вверх - ровно столько раз текущей вещи надо было повисеть на батарее, чтобы через M минут она высушилась. Если оказывается, что сумма округленных вверх (a_i - m) / (k - 1) больше M, то за M минут все вещи высохнуть не успеют.
Значит мы можем бинарным поиском искать M, которое и будет ответом.
Итоговая асимптотика - O(NlogN) - мы O(logN) раз перебираем M тратя каждый раз на проверку O(N) операций

C++:

#include <iostream> #include <vector> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, l = 0, r = 0; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; r = max(r, a[i]); } cin >> k; if (k == 1) { cout << r; return 0; } while (l < r - 1) { int m = (l + r) / 2; int left = m; for (int i = 0; i < n; i++) { if (a[i] > m) { left -= (a[i] - m + k - 2) / (k - 1); } } if (left < 0) { l = m + 1; } else { r = m; } } cout << l; }

Что-то даже не пришло в голову использовать бинпоиск по ответу) Большое спасибо за хорошее решение.