Advertisement

NOIP题目(挤奶 cow)

阅读量:
复制代码
    问题 B: 【NOIP模拟赛】拥挤的奶牛
    时间限制: 1 Sec  内存限制: 128 MB
    提交: 10  解决: 2
    [提交] [状态] [讨论版] [命题人:xingxing]
    题目描述
    有N头奶牛(1<=N<=50000)排成一列。第i奶牛有一个坐标x[i]和一个身高h[i]。如果在奶牛i的左边距离d(1<=d<=1000000000,)以内有一头奶牛的身高不小于2*h[i],且右边距离d以内也有一头奶牛的身高不小于2*h[i],则奶牛i会觉得很拥挤。请找出有多少头这样的奶牛。 
    输入
    输入格式:第一行两个整数N和d。 
    接下来N行,第i+1行包含整数x(i)和h(i)。所有奶牛的位置均不相等。 
    输出
    输出格式:有多少头奶牛会觉得拥挤。
    样例输入 Copy
    6 4
    10 3
    6 2
    5 3
    9 7
    3 6
    11 2
    样例输出	Copy
    2
    拿到这道题的第一方法就是枚举,但是超时了,只拿了60分,我也从这道题了解到了单调队列,但我还是不清楚什么时候才用队列,怎样才能想到队列,看了一位博客的方法后,我也用优先队列写了一遍,实在是巧妙啊,请各位大神请教什么时候才用队列;
    
    

全部评论 (0)

还没有任何评论哟~