Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/25: Рейтинг темы: голосов - 25, средняя оценка - 5.00
3 / 3 / 0
Регистрация: 26.11.2017
Сообщений: 30

Определить количество столбов находящихся в пределах заданной ширины проема

02.01.2019, 08:11. Показов 5228. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали N столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум W. Теперь им придётся выкапывать некоторые столбы.

Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной W.

Входные данные
Первая строка содержит два целых числа N и W — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что 0 <=N <=30000 и что 0 <=W <=60000.

Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числа L и R — координаты левого и правого конца этой стороны (L <R). Далее следуют N чисел — координаты вкопанных столбов. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 30000. Гарантируется, что все столбы вкопаны между левым и правым концами стороны.

Выходные данные
В первой строке выходного файла должно быть минимальное число столбов, которые надо выкопать. Далее должны следовать номера этих столбов. Столбы нумеруются в том порядке, как они указаны во входном файле, начиная с 1.

Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите в выходной файл одну строку, содержащую число -1.
ввод
3 2
2 6
3 4 5
вывод
1
2
ввод
3 2
1 6
4 3 5
вывод
0
ввод
3 5
1 7
5 3 4
вывод
3
2
1
3

Написал решение,но не проходит на нескольких тестах,помогите найти ошибку.
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
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,w,left,right;
    cin>>n>>w>>left>>right;
    vector<pair<int,int>> A(n+2);
    A[0].first=left;
    A[0].second=0;
    A[n+1].first=right;
    A[n+1].second=n+1;
    for (int i=1;i<=n;++i)
    {
        cin>>A[i].first;
        A[i].second=i;
    }
    sort(A.begin(),A.end());
    int l=0,r=n+1;
    int x1,x2,dist=1e9;
    while (l<r)
    {
        int m=(l+r)/2;
        if (A[r].first-A[l].first>=w)
        {
 
            if (r-l-1<dist)
            {
                dist=r-l-1;
                x1=l+1;
                x2=r-1;
            }
            l++;
        }
        if (A[r].first-A[l].first<w)
        {
            r--;
            l=0;
        }
    }
    if (dist==1e9)
        cout<<-1;
    else{
        cout<<dist<<endl;
    for (int i=x1;i<=x2;++i)
        cout<<A[i].second<<endl;
    }
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
02.01.2019, 08:11
Ответы с готовыми решениями:

Console: выравнивание текста в пределах заданной ширины
Выдержка из учебника и результат работы моей программы заскриншотил. Мой код: using System; class Test{ public static void...

Найти по каждому третьему столбцу матрицы среднее значение и количество элементов, находящихся в пределах
Задание: В заданном массиве A(M, N), (M≤7, N≤10) найти по каждому третьему столбцу среднее значение и количество элементов, находящихся в...

Количество чисел, находящихся на заданной глубине
Для произвольного списка вычислить количество чисел на заданной глубине ((1 A) ((3 4) (D C)) (2) (A)) 2 –&gt; 2 Хотел задать константу...

1
0 / 0 / 0
Регистрация: 30.04.2016
Сообщений: 1
08.03.2019, 12:53
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
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1e9
#define DINF (1. / 0.)
 
int main()
{
    cin.tie(); cout.tie(); cerr.tie();
    ios_base::sync_with_stdio(false);
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
 
    unsigned N; long long W; cin >> N >> W;
 
    long long center = 1e6;
    vector<unsigned> pos((center << 1) + 1);
 
    vector<long long> cord(N + 2);
    cin >> cord[0] >> cord.back();
    for (unsigned i = 1; i <= N; i++)
    {
        cin >> cord[i];
        pos[center + cord[i]] = i;
    }
 
    sort(cord.begin(), cord.end());
 
    unsigned ans = INF;
    unsigned be, en;
    for (unsigned i = 0; i <= N; i++)
    {
        unsigned l = i + 1;
        unsigned r = N + 1;
 
        while (l < r)
        {
            unsigned m = (l + r) >> 1;
            if (cord[m] - cord[i] >= W)
                r = m;
            else
                l = m + 1;
        }
 
        if (cord[l] - cord[i] >= W && l - i - 1 < ans)
        {
            ans = l - i - 1;
            be = i + 1;
            en = l - 1;
        }
    }
 
    if (ans == INF)
    {
        cout << -1;
    }
    else
    {
        cout << ans << endl;
        for (unsigned i = be; i <= en; i++)
        {
            cout << pos[center + cord[i]] << endl;
        }
    }
 
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
08.03.2019, 12:53
Помогаю со студенческими работами здесь

Определить количество чисел, лежащих в пределах от -2 до 12.
С клавиатуры вводится n чисел. Определить количество чисел, лежащих в пределах от -2 до 12. Задача на цикл.

Определить количество элементов, находящихся в интервале
Дан одномерный массив размерностью 10, заполненный целыми числами, введенными с клавиатуры. Определить количество элементов, находящихся в...

Определить количество молекул для v, изменяющегося в пределах ...
Кол-во вещества v (в молях) равно отношению числа молекул N в данном теле к постоянной Авогадро Na = 6*10(-23 степени), т.е к числу молекул...

Определить количество точек, находящихся внутри прямоугольника
Задано n точек. Определить, сколько из них находится внутри прямоугольника

Определить количество элементов массива, находящихся в интервале от 1 до 12
Дан одномерный массив размерностью 10, заполненный целыми числами, введенными с клавиатуры. Определить количество элементов, находящихся в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru