Я делаю программу, которая находит подмассив максимальной длины, сумма которого ближе всего к 0.
На самом деле я пытался решить этот вопрос: http://opc.iarcs.org.in/index.php/problems/DEVIOUS , но когда я отправляю свой код, он дает правильный ответ только в 50% тестовых случаев.
Мой код работает нормально, и даже дает правильный ответ для моих собственных тестовых случаев, поэтому мне нужен тестовый пример, чтобы доказать, что мой код / алгоритм неверен, чтобы я мог найти ошибку в своем коде.
Это мой алгоритм,
- Создайте массив ‘temp’, равный размеру входного массива, инициализируйте все элементы temp так, чтобы temp [i] = сумма всех элементов до input [i].
- Отсортируйте массив 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% входных данных
Другими словами, если прибыль / убытки на станциях равны 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 меньше)?
Других решений пока нет …