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

@ERW1N · Регистрация: 29.10.2016

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

И снова здравствуйте.Условие:даны N точек с двойной точностью(точки заданные вещественными числами ). Определить минимальное количество отрезков единичной длины необходимых для того чтоб покрыть все эти точки(Время 300 мс). Нужна только идея решения.Пробовал отбросить дробную часть и посчитать количество разных чисел но не помогло.

MrGluck · 14.06.2017, 16:08

Комментарий модератора

ERW1N, запрещено дублировать темы

@ERW1N · 14.06.2017, 16:09 **[ТС]**

Случайно

@Cuellius · 14.06.2017, 16:19

C++

#include <algorithm>
#include <cstdio>
 
int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    double *a = new double[n];
    for(int i = 0; i < n; i++) scanf("%lf", a + i);
    
    std::sort(a, a + n);
    
    double x = a[0] - 3; //начальная точка нашего текущего отрезка
    for(int i = 0; i < n; i++)
    {
        if(x + 1 < a[i]) //если отрезок не покрывает точку a[i]
        {
            x = a[i];
            ans++;
        }
    }
    
    printf("%d\n", ans);
    
    delete[] a;
    return 0;
}

@ERW1N 0 / 0 / 1 Регистрация: 29.10.2016 Сообщений: 71
		1
	Определить минимальное количество отрезков единичной длины необходимых для того чтоб покрыть все точки 14.06.2017, 14:37. Показов 3414. Ответов 3 Метки с (Все метки) И снова здравствуйте.Условие:даны N точек с двойной точностью(точки заданные вещественными числами ). Определить минимальное количество отрезков единичной длины необходимых для того чтоб покрыть все эти точки(Время 300 мс). Нужна только идея решения.Пробовал отбросить дробную часть и посчитать количество разных чисел но не помогло. 0

@ERW1N 0 / 0 / 1 Регистрация: 29.10.2016 Сообщений: 71
	14.06.2017, 16:09 [ТС]	3
	Случайно 0

	14.06.2017, 16:19

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

Решение