最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 问题 BC: L17-6 单调队列优化dp2 - 作业

    正文概述 网友投稿   2026-01-22 16:13:44  

    题目描述

    有N(1 <= N <= 50,000)头羊沿着一维的栅栏吃草,第i头羊在目标点x[i],它的身高是 h[i]( (1 <=x[i],h[i] <= 1,000,000,000)。当一头羊左边D距离内而且右边D距离内有身高至少是它的两倍的羊(1 <= D <= 1,000,000,000),它就会觉得拥挤。 请计算觉得拥挤的羊的数量。

    输入

    第一行两个整数 N、D,由空格隔开。 第2到第N+1行,每行两个整数x[i],h[i],描述一头羊。

    输出

    输出一个整数,表示觉得拥挤的羊的数量。

    样例输入

    6 4 
    10 3 
    6 2 
    5 3 
    9 7 
    3 6 
    11 2 

    样例输出

    2
    信息学奥赛网,一个优质的源码资源平台!
    信息学奥赛网 » 问题 BC: L17-6 单调队列优化dp2 - 作业