Самый длинный подмассив массива состоящий из одинаковых чисел, с удалением до k элементов

@Tonendd · Регистрация: 06.06.2023

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста с задачей

Дан массив длины n и число k. Необходимо максимизировать количество одинаковых чисел, идущих подряд, удаляя из массива до k (включительно) элементов.

Формат входных данных
В первой строке входа заданы два целых числа n и k (1 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 1 000 000) — длина массива и количествоо чисел которые можно удалить. В следующей строке заданы n целых чисел c_i (1 ≤ c_i ≤ n) — элементы массива

Формат результата
Выведите одно число — максимальную длину последовательности, которую можно получить, удаляя числа

Примеры
Входные данные
8 2
2 4 4 2 1 4 2 4
Результат работы
3

@alexu_007 · 21.02.2026, 13:25

Сообщение от Igor3D

Но все равно - красивое, неочевидное (во всяком случае для меня) решение

А кто автор линейного решения?

@igorrr37 · 21.02.2026, 15:06

Сообщение от alexu_007

кто автор линейного решения?

так у него же и есть линейное. А то - моё

Добавлено через 5 минут
вот ещё решения с leetcode

@gunslinger · 21.02.2026, 15:29

Вот два варианта кода от чат жпт (2 теста на leetcode и 1 из этой темы вроде как проходят):

O(N) worst-case

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        int n = nums.size();
 
        // group positions by value
        unordered_map<int, vector<int>> pos;
        pos.reserve(n);
 
        for (int i = 0; i < n; ++i)
            pos[nums[i]].push_back(i);
 
        int ans = 1;
 
        // process each value independently
        for (auto& [val, p] : pos) {
            int l = 0;
            for (int r = 0; r < (int)p.size(); ++r) {
                // deletions needed
                while (p[r] - p[l] - (r - l) > k)
                    ++l;
                ans = max(ans, r - l + 1);
            }
        }
        return ans;
    }
};

N ≤ 10⁶

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        const int n = nums.size();
        if (n == 0) return 0;
 
        /* 1. Coordinate compression */
        vector<int> vals(nums);
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
 
        const int U = vals.size();
        for (int& x : nums)
            x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
 
        /* 2. Build positions */
        vector<vector<int>> pos(U);
        pos.reserve(U);
        for (int i = 0; i < n; ++i)
            pos[nums[i]].push_back(i);
 
        int ans = 1;
 
        /* 3. Sliding window on positions */
        for (int v = 0; v < U; ++v) {
            auto& p = pos[v];
            const int m = p.size();
            if (m <= ans) continue;   // pruning
 
            int l = 0;
            for (int r = 0; r < m; ++r) {
                // deletions = (p[r] - p[l]) - (r - l)
                while (p[r] - p[l] - (r - l) > k)
                    ++l;
                ans = max(ans, r - l + 1);
            }
        }
        return ans;
    }
};

Вариант с тестами

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        const int n = (int)nums.size();
        if (n == 0) return 0;
 
        // value compression
        vector<int> vals = nums;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
 
        const int m = (int)vals.size();
        vector<vector<int>> pos(m);
        pos.reserve(m);
 
        for (int i = 0; i < n; ++i) {
            int id = lower_bound(vals.begin(), vals.end(), nums[i]) - vals.begin();
            pos[id].push_back(i);
        }
 
        int ans = 1;
 
        for (int id = 0; id < m; ++id) {
            const auto& p = pos[id];
            int l = 0;
            for (int r = 0; r < (int)p.size(); ++r) {
                while (p[r] - p[l] - (r - l) > k) {
                    ++l;
                }
                ans = max(ans, r - l + 1);
            }
        }
        return ans;
    }
};
 
#ifdef LOCAL_TEST
// =======================================================
// ===================== HARNESS ==========================
// =======================================================
 
int solve_strict(vector<int> nums, int k) {
    Solution s;
    return s.longestEqualSubarray(nums, k);
}
 
// ===== Reference slow solution (O(N^2)) for fuzzing =====
int solve_slow(vector<int>& nums, int k) {
    int n = nums.size();
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        unordered_map<int,int> cnt;
        int removed = 0;
        for (int j = i; j < n; ++j) {
            cnt[nums[j]]++;
            int len = j - i + 1;
            int best = 0;
            for (auto& [_, v] : cnt) best = max(best, v);
            removed = len - best;
            if (removed <= k) ans = max(ans, best);
        }
    }
    return ans;
}
 
void run_test(const vector<int>& nums, int k, int expected = -1) {
    vector<int> copy = nums;
    int a = solve_strict(copy, k);
 
    if (expected != -1 && a != expected) {
        cerr << "WRONG ANSWER\n";
        cerr << "k=" << k << "\nnums: ";
        for (int x : nums) cerr << x << " ";
        cerr << "\nexpected=" << expected << " got=" << a << "\n";
        exit(1);
    }
}
 
// =======================================================
// ====================== FUZZER ==========================
// =======================================================
 
void fuzz_tests() {
    mt19937 rng(123456);
 
    for (int it = 0; it < 5000; ++it) {
        int n = rng() % 40 + 1;
        int k = rng() % n;
        vector<int> a(n);
 
        int mode = rng() % 4;
        if (mode == 0) {                 // random
            for (int i = 0; i < n; i++) a[i] = rng() % 5;
        } else if (mode == 1) {          // alternating
            for (int i = 0; i < n; i++) a[i] = i & 1;
        } else if (mode == 2) {          // dense
            for (int i = 0; i < n; i++) a[i] = (rng() % 3 == 0);
        } else {                         // unique
            for (int i = 0; i < n; i++) a[i] = i;
        }
 
        vector<int> b = a;
        int fast = solve_strict(a, k);
        int slow = solve_slow(b, k);
 
        if (fast != slow) {
            cerr << "FUZZ FAIL\n";
            cerr << "k=" << k << "\nnums: ";
            for (int x : a) cerr << x << " ";
            cerr << "\nfast=" << fast << " slow=" << slow << "\n";
            exit(1);
        }
    }
    cerr << "FUZZ PASSED\n";
}
 
// =======================================================
// ======================= MAIN ===========================
// =======================================================
 
int main() {
    // unit tests
    run_test({5}, 0, 1);
    run_test({7,7}, 0, 2);
    run_test({7,8}, 0, 1);
    run_test({1,3,2,3,1,3}, 3, 3);
    run_test({2,1,2,1,2,1,2}, 3, 4);
    run_test({1,1,1,2,3,4,1,1}, 2, 5);
 
    cerr << "UNIT TESTS PASSED\n";
 
    // fuzz
    fuzz_tests();
 
    return 0;
}
#endif

Новые блоги и статьи Все статьи Все блоги /
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Tonendd 0 / 0 / 0 Регистрация: 06.06.2023 Сообщений: 9

	Самый длинный подмассив массива состоящий из одинаковых чисел, с удалением до k элементов 31.08.2023, 20:17. Показов 5588. Ответов 42 Метки нет (Все метки) Помогите пожалуйста с задачей Дан массив длины n и число k. Необходимо максимизировать количество одинаковых чисел, идущих подряд, удаляя из массива до k (включительно) элементов. Формат входных данных В первой строке входа заданы два целых числа n и k (1 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 1 000 000) — длина массива и количествоо чисел которые можно удалить. В следующей строке заданы n целых чисел c_i (1 ≤ c_i ≤ n) — элементы массива Формат результата Выведите одно число — максимальную длину последовательности, которую можно получить, удаляя числа Примеры Входные данные 8 2 2 4 4 2 1 4 2 4 Результат работы 3 0