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

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

02.01.2019, 08:11. Показов 2544. Ответов 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
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.01.2019, 08:11
Ответы с готовыми решениями:

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

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

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

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

1
0 / 0 / 0
Регистрация: 30.04.2016
Сообщений: 1
08.03.2019, 12:53 2
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.03.2019, 12:53

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru