Решение задачи Дровосеки с Codeforces

Без пояснения   Просмотров: 25


Маленькая девочка Сьюзи каждый день слушает сказки перед сном. Сегодняшняя сказка была про дровосеков, поэтому маленькая девочка сразу же начала представлять себе, как дровосеки рубят деревья, и в её мыслях родилась ситуация, описанная ниже.

Есть n деревьев, расположенных вдоль дороги в точках с координатами x1, x2, ... , xn. Каждое дерево имеет свою высоту hi. Дерево можно срубить и повалить влево или вправо. Тогда оно будет занимать отрезки [xi - hi, xi] и [xi;xi + hi] соответственно. Пока дерево не срублено, оно занимает точку с координатами xi. Дерево можно повалить, если на отрезке, который оно должно занимать после сваливания, нет ни одной занятой точки. Дровосеки хотят заготовить как можно большее число деревьев, поэтому Сьюзи стало интересно, какое наибольшее количество деревьев можно повалить.

Код

#include<stdio.h>
int a[100001], b[100001], n, i, j, s = 2;
int main(){
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d%d",&a[i],&b[i]);
	for(i = 1;i < n - 1; i++){
		if(a[i] - a[i - 1] > b[i])
            s++;
		else if(a[i + 1] - a[i] > b[i]){ 
		    s++;
            a[i] += b[i];
        }    
	}
	printf("%d",n == 1 ? 1:s);
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться