Мне нужен тестовый пример, чтобы доказать, что мой алгоритм / код неверен

Я делаю программу, которая находит подмассив максимальной длины, сумма которого ближе всего к 0.
На самом деле я пытался решить этот вопрос: http://opc.iarcs.org.in/index.php/problems/DEVIOUS , но когда я отправляю свой код, он дает правильный ответ только в 50% тестовых случаев.
Мой код работает нормально, и даже дает правильный ответ для моих собственных тестовых случаев, поэтому мне нужен тестовый пример, чтобы доказать, что мой код / ​​алгоритм неверен, чтобы я мог найти ошибку в своем коде.

Это мой алгоритм,

  1. Создайте массив ‘temp’, равный размеру входного массива, инициализируйте все элементы temp так, чтобы temp [i] = сумма всех элементов до input [i].
  2. Отсортируйте массив temp, найдите ‘i’ в temp так, чтобы temp [i-1] — temp [i] был ближе всего к 0

Вот мой код для решения проблемы по ссылке выше.

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <limits.h>

using namespace std;

struct element{
int index;
int value;
};

bool compare(element a, element b){
return a.value < b.value;
}

int main(){
int n;
cin >> n;
int array [n];
element elements[n];
int sum = 0;

for(int i = 0 ;i < n; i ++){
cin >> array[i];
sum = sum + array[i];
elements[i].index = i;
elements[i].value = sum;
}

sort(elements,elements+n,compare);

int diff = INT_MAX;
int i1 = 0,i2 = 0;
for(int i = 1;i < n;i ++){
int temp = elements[i].value - elements[i-1].value;
if(temp < diff){
diff = temp;
i1 = elements[i].index;
i2 = elements[i-1].index;
}
else if(temp == diff){
if(abs(elements[i].index - elements[i-1].index) > abs(i1-i2)){
i1 = elements[i].index;
i2 = elements[i-1].index;
}
}
}

diff = 0;
int s,e;
if(i1 >= i2){
e = i1, s = i2+1;
}else{
s = i1+1, e = i2;
}

for(int i = s;i <= e ; i++){
diff = diff+array[i];
}
cout << diff << endl;

cout << s+1 << " " << e+1;

return 0;
}

РЕДАКТИРОВАТЬ: я нашел ошибку в своем коде и отредактировал ее, теперь она дает правильный ответ для 80% входных данных

3

Решение

Другими словами, если прибыль / убытки на станциях равны p1, p2, …,
Министр хотел бы передать последовательность i, i + 1, …, j такая
что абсолютное значение pi + pi + 1 + … + pj сведено к минимуму. Если там
более одной последовательности с этим минимальным абсолютным значением, то он
хотел бы передать самый длинный

Я думаю, что ваш алгоритм немного не так

temp [i] = сумма всех элементов до входа [i] Сортировка временного массива

Начало последовательности вполне может быть другой позицией, чем начало массива — это может быть подпоследовательность, не забывайте.

-1 | -2 | 10 | 5 |-10 | 6

|    |    | x | x  | x

edit2: убрал неправильное объяснение, теперь я посмотрел код —

if(temp < diff){
diff = temp;
i1 = elements[i].index;
i2 = elements[i-1].index;
}

У вас есть предпочтение -ve номера (потеря). Может ли случиться так, что промахы — это то, где есть близкое к нулю число, потому что оно немного меньше -ve или + ve (но где значение abs меньше)?

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]