C/C++

Решите задачу на любом языке. Желательно на с++.

Вы являетесь автором раунда Codeforces и подготовили n задач, которые вы собираетесь задать, причем задача i имеет сложность ai . Вы будете выполнять следующий процесс: удалить некоторые (возможно, ноль) задач из списка; переставить оставшиеся задачи в любом порядке, который вы пожелаете. Раунд считается сбалансированным, если и только если абсолютная разница между сложностью любых двух последовательных задач не превышает k (то есть меньше или равен k ). Какое минимальное количество задач нужно удалить, чтобы расстановка задач была сбалансированной? Входные данные Первая строка содержит одно целое число t (1≤t≤1000 ) — количество наборов входных данных. Первая строка каждого набора содержит два положительных целых числа n (1≤n≤2⋅105 ) и k (1≤k≤109 ) — количество задач и максимально допустимая абсолютная разница между последовательными задачами. Вторая строка каждого набора содержит n целых чисел, разделенных пробелами, ai (1≤ai≤109 ) — сложность каждой задачи. Обратите внимание, что сумма n по всем тестам не превышает 2⋅105 . Выходные данные Для каждого набора входных данных выведите одно целое число — минимальное количество задач, которые нужно удалить, чтобы расстановка задач была сбалансированной.
Пример входные данные
7 5 1 1 2 4 5 6 1 2 10 8 3 17 3 1 20 12 5 17 12 4 2 2 4 6 8 5 3 2 3 19 10 8 3 4 1 10 5 8 1 8 3 1 4 5 10 7 3
выходные данные
2 0 5 0 3 1 4
Примечание В первом примере мы можем удалить первые 2 задачи и составить набор, используя задачи со сложностями [4,5,6] , с разницей между соседними задачами равной |5−4|=1≤1 и |6−5|=1≤1 . Во втором примере мы можем взять одну задачу и составить раунд, используя задачу со сложностью 10 .
ЗШ
Зоир Шукуров
455 
 #include 

#include 

#include 

using namespace std; 

 

int check(vector& vec, int dim) 

{ 

	int max_len = 1, len = 1; 

	sort(vec.begin(), vec.end()); 

	for (auto i = vec.begin()+1; i!= vec.end();i++) 

	{ 

		if (*i - *(i - 1) > n; 

	while (n--) 

	{ 

		size_t ssize, dif; 

		cin >> ssize >> dif; 

		if (ssize == 1)  

		{ 

			cin >> dif; 

			results.push_back(0); continue; 

		} 

		vector vec(ssize);  

		for (auto& i : vec) cin >> i; 

		results.push_back(check(vec, dif)); 

	} 

	cout
АС
Андрей Сумачев
51 417
Лучший ответ
>Первая строка содержит одно целое число t
>Пример входные данные
7 5 1 1 2 4 5 6 1 2 10 8 3 17 3 1 20 12 5 17 12 4 2 2 4 6 8 5 3 2 3 19 10 8 3 4 1 10 5 8 1 8 3 1 4 5 10 7 3

Хренасе "одно число"! Ты там ничего не попутал?
Ихтияр Шеранов
Ихтияр Шеранов
50 754
Зоир Шукуров входные данные

7

5 1

1 2 4 5 6

1 2

10

8 3

17 3 1 20 12 5 17 12

4 2

2 4 6 8

5 3

2 3 19 10 8

3 4

1 10 5

8 1

8 3 1 4 5 10 7 3

выходные данные

2

0

5

0

3

1

4 
 #include  

#include  

#include 



using namespace std;



class Sequence { 

public: 

    Sequence() : a(0) {} 

    explicit Sequence(const size_t n, const int a) noexcept : a(a) { 

        seq.resize(n); 

    } 

    size_t task() noexcept { 

        const auto n = seq.size(); 

        if (n < 2) return 0; 

        sort(seq.begin(), seq.end()); 

        size_t m = 0; 

        size_t k = 1; 

        for (size_t i = 1; i < n; ++i) { 

            if (seq[i] - seq[i - 1]  m) m = k; 

        return n - m; 

    } 

private: 

    int a; 

    vector seq; 

    friend istream& operator>>(istream& inp, Sequence& s) { 

        for (auto& x : s.seq) inp >> x; 

        return inp; 

    } 

};



class Task { 

public: 

    explicit Task(const size_t n) noexcept { 

        box.resize(n); 

    } 

private: 

    vector box; 

    vector result() noexcept { 

        const auto length = box.size(); 

        vector res(length); 

        for (size_t i = 0; i < length; ++i) { 

            res[i] = box[i].task(); 

        } 

        return res; 

    } 

    friend istream& operator>>(istream& inp, Task& r) { 

        size_t n; 

        int a; 

        for (auto& x : r.box) { 

            inp >> n >> a; 

            Sequence seq{ n, a }; 

            cin >> seq; 

            x = seq; 

        } 

        return inp; 

    } 

    friend ostream& operator task; 

    cout
ЮА
Юрий Афанасьев
62 297
Юрий Афанасьев 27 строка (исправление)
 if (k > m && k > 1) m = k;
сорян географию не учил
Эдуард Клеттер
Эдуард Клеттер
145

Похожие вопросы