Найти минимальное среднее любого среза, содержащего как минимум два элемента в массиве

Question

Полный вопрос: Минимальная средняя двухсекционная кодильность

Я не понимаю, почему мой код не работает.

Я знаю правильный ответ,но я не могу найти противоположный пример для моего кода:

struct partaverg {
    long double min;
    int slice;
};

long long sumfun(int arr[], int N) {
    int sum = 0;
    for (int i = 0; i < N; ++i)
        sum += arr[i];
    return sum;
}

int solution(int A[], int N) {
    long long sum;
    long double new_average;

    int left = 0;
    int right = N - 1;
    long double numofnum;
    long double leftaverg, rightaverg;
    sum = sumfun(A, N);
    struct partaverg result;
    new_average = result.min = sum / (long double)N;
    result.slice = 0;
    while (left + 1 < right) {
        numofnum = right - left;
        leftaverg = (sum - A[left]) / numofnum;
        rightaverg = (sum - A[right]) / numofnum;
        if (leftaverg > rightaverg) {
            sum -= A[right--];
            new_average = rightaverg;
        } else {
            sum -= A[left++];
            new_average = leftaverg;
        }
        if (result.min > new_average) {
            result.min=new_average;
            result.slice=left;
        }
    }
    return result.slice;
}

Answer 1

Проблема с вашим алгоритмом возникает тогда, когда текущий срез содержит одинаковое число в самой левой и самой правой позиции. Какой номер вы удалите? Левый или правый?

Ваш текущий алгоритм всегда удаляет левое число, но это может быть неверно. Рассмотрим:

int arr[4] = {1,9, 10, 1 };

// left average = (1 + 9 + 10) /3
// right average = (9 + 10 + 1) /3

Левое среднее и правое среднее одинаковы, поэтому ваш код удаляет левое число и переходит к следующему фрагменту:

{9, 10, 1 };

что не так. Теперь вы больше не можете достичь правильного результата:

{1,9};