Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помощ с оптимизацией кода

Артем Ка Ученик (204), на голосовании 5 месяцев назад
Решаю эту задачу
 #include  
using namespace std;
#define int int64_t
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector vec(n);
for (int i = 0; i < n; ++i) cin >> vec[i];
int ans = 0;
int k = -1;
for (int h = 0; h < n; ++h) {
if (vec[h] > k) k = vec[h];
} // k это число m по условию задачи

for (int i = 0; i < n; ++i) {
for (int s = 2; s <= k; ++s) {
int l = vec[i] % s;
int anss = 1;
for (int h = i + 1; h < n; ++h) {
if (vec[h] % s == l) anss++;
else break;
}
if (anss > ans) ans = anss;
}
}
cout << ans << "\n";
}
return 0;
}
Мое решение не проходит по времени, я думаю что он неэффективно перебирает k, подскажите как можно оптимизировать код
Голосование за лучший ответ
Scythe Моя мама Мастер (1053) 6 месяцев назад
Там ошибка, перепишите
Артем КаУченик (204) 6 месяцев назад
это понятно, я хочу понять как оптимизировать код
Jurijus Zaksas Искусственный Интеллект (445772) 6 месяцев назад
Я смотрю на входные данные.
Там в начале идет типа

4
5
1 2 3 4 5

5 - это количество элементов в массиве, ладно.
А что такое 4?

>// k это число m по условию задачи
А почему бы m не назвать m? Чтобы никто не догадался?

Дык вот, если там в начале вводится то самое m, то задача сия имеет сложность O(n). А у тебя, судя по тройному циклу, O(n^3). Просто не делай так.
Артем КаУченик (204) 6 месяцев назад
чило m не вводится)
V̲i̲s̲t̲a̲s̲t̲e̲r̲ Искусственный Интеллект (263972) 6 месяцев назад
 #include   
using namespace std;
#define int int64_t

signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector vec(n);
for (int i = 0; i < n; ++i) cin >> vec[i];

// Находим максимальный элемент массива
int k = *max_element(vec.begin(), vec.end());

// unordered_map для подсчета числа элементов с одинаковым остатком
unordered_map cnt;

// Подсчет количества элементов с одинаковым остатком
for (int i = 0; i < n; ++i) {
for (int s = 2; s <= k; ++s) {
if (vec[i] % s == 0) {
cnt[s]++;
}
}
}

// Находим максимальное значение в unordered_map
int ans = 0;
for (auto& [key, value] : cnt) {
ans = max(ans, value);
}

cout << ans << "\n";
}
return 0;
}
Артем КаУченик (204) 6 месяцев назад
Здравствуйте, ваш код выглядит лучше чем мой, но он не учитывает что братсво это рядом стоящиен элементы. сейчас попробую переделать под условие задачи
Артем КаУченик (204) 6 месяцев назад
В вашем коде ищется по всему массиву, а если его переделать под братство, то получится тоже самое что у меня
Александр Искусственный Интеллект (301569) 6 месяцев назад
а чё другой категории для вопроса не нашёл? типа где шёл, там и присел?
Артем КаУченик (204) 6 месяцев назад
ой, что-то даже не заметил сорян)
Похожие вопросы