программа долго выполняется (c++)

136

18 апреля 2019, 18:30

Вот программа:

#include <iostream>
#include <algorithm>
using namespace std;
void check(int array[],int size);
int Guest = 0;
int main()
{
    int n;
    cin>>n;
    if(n == 1){
        int l;
        cin>>l;
        cout<<l/2+l%2;
        return 0;
    }
    int *arr = new int[n];
    for (int i = 0; i < n; ++i) {
        cin>>arr[i];
    }
    check(arr,n);
    return 0;
}
void check(int arr[], int size){
    sort(arr,arr + size);
    if(abs(Guest - arr[size-1]) == 1){
        cout<<max(Guest,arr[size-1]);
        return ;
    }
    arr[size-1]--;
    Guest++;
    check(arr,size);
}

что она должна делать: Вот

Говорят программа слишком медленная.Как исправить?

Answer 1

Ну на каждом шагу пересортировывать - это, конечно, не годится.

Значительно более быстрый вариант - с использованием бинарного поиска. Вкратце:
Отсортируем массив по возрастанию.
Создадим второй массив с накопленной суммой (С[i] = C[i-1] + A[i])

Выберем индекс i (на рисунке i=4)
Если срезать стопки блинов по высоте A[i], то останется R = С[i] + A[i]*(N-i) (серое + красное), а остальное Q =C[N]-R (синее) перейдёт неофиту.
Если Q > A[i], то i надо увеличивать, если меньше - уменьшать.

Answer 2

Задачу можно решить за один проход по предварительно отсортированному в возрастающем порядке массиву исходя из следующего уравнения:

a - x >= c + x * (i + 1)

где:

a - текущий элемент массива
x - значение на которое можно гарантированно уменьшить этот и все предыдущие элементы
c - счетчик, куда сбрасывается остаток с каждого элемента. Это тарелка нового гостя.

Соответсвенно:

x = (a - c) / (i + 2)

Алгоритм:

int64_t c = 0;
int64_t m = arr[0]; // искомый результат
for (int i=0; i<arr.size(); ++i) {
  int64_t a = arr[i];
  if (a <= c) break; // #1
  int64_t x = (a - c) / (i + 2);
  if (i < arr.size() - 1 && x > a - arr[i + 1]) { // #2
    x = a - arr[i + 1];
  }
  c += (i + 1) * x;
  m = a - x;
}

Коментарии:

Проходиться по массиву имеет смысл только до тех пор пока значение накопленных в счетчике блинов не превышает значения текущего элемента (a > c).
На каждой итерации имеет смысл срезать не более чем разница между текущим значением и последующим, если оно имеется.

Полностью пример:

#include <algorithm>
#include <iostream>
#include <vector>
template <typename T>
void print(const std::string& title, const T& arr)
{
  std::cout << title;
  for (const auto& x: arr) {
    std::cout << ' ' << x;
  }
  std::cout << std::endl;
}
int main(int argc, char** argv)
{
  std::vector<int64_t> arr {1, 19, 1, 15, 20};
  print("orig:   ", arr);
  std::sort(arr.begin(), arr.end(), std::greater<decltype(arr)::value_type>());
  print("sorted: ", arr);
  int64_t c = 0;
  int64_t m = arr[0];
  for (int i=0; i<arr.size(); ++i) {
    int64_t a = arr[i];
    if (a <= c) break;
    int64_t x = (a - c) / (i + 2);
    if (i < arr.size() - 1 && x > a - arr[i + 1]) {
      x = a - arr[i + 1];
    }
    c += (i + 1) * x;
    m = a - x;
  }
  for (auto& x: arr) {
    if (x < m) break;
    x = m;
  }
  arr.push_back(c);
  print("output: ", arr);
  std::cout << "m=" << m << " c=" << c << std::endl;
  return 0;
}

Результат:

orig:    1 19 1 15 20
sorted:  20 19 15 1 1
output:  14 14 14 1 1 12
m=14 c=12

Upd: Важный момент - при проходе по массиву, на самом деле, нету смысла уменьшать элементы массива. Именно это и реализовано. Двигаясь от начала массива, алгоритм оценивает достаточен ли запас свободного места в 'тарелке нового гостя'. И если это так, то расчитывается новый максимум m.