BZOJ 3314 [Usaco2013 Nov]Crowded Cows：单调队列

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3314

题意：

　　N头牛在一个坐标轴上，每头牛有个高度。现给出一个距离值D。

　　如果某头牛在它的左边，在距离D的范围内，如果找到某个牛的高度至少是它的两倍，且在右边也能找到这样的牛的话。则此牛会感觉到不舒服。

　　问有多少头会感到不舒服。

题解：

　　从左到右、从右到左两遍单调队列。

　　单调性：

　　　　（1）坐标x递增。

　　　　（2）高度h递减。

　　维护单调性：

　　　　（1）从队首开始，所有与当前牛i的距离超过d的，以后都不会再用到。

　　　　（2）从队尾开始，所有高度 <= 当前高度h[i]的，都不会再用到，因为当前牛i一定比前面的更优（又高又近）。

　　　　（3）最后再将i压入队尾。

　　每次判断一下之前最高的牛（队首）是不是h[i]的两倍，如果是则cnt[i]++。

　　最后统计一下cnt[i] == 2的个数就好。

AC Code:

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define MAX_N 50005

using namespace std;

struct Data

{

    int x;

    int h;

    Data(int _x,int _h)

    {

        x=_x;

        h=_h;

    }

    Data(){}

    friend bool operator < (const Data &a,const Data &b)

    {

        return a.x<b.x;

    }

};

int n,d;

int head;

int tail;

int ans=;

int q[MAX_N];

int cnt[MAX_N];

Data dat[MAX_N];

void read()

{

    cin>>n>>d;

    for(int i=;i<n;i++)

    {

        cin>>dat[i].x>>dat[i].h;

    }

}

void solve()

{

    sort(dat,dat+n);

    memset(cnt,,sizeof(cnt));

    head=;

    tail=;

    for(int i=;i<n;i++)

    {

        while(head<tail && dat[i].x-dat[q[head]].x>d) head++;

        while(head<tail && dat[q[tail-]].h<=dat[i].h) tail--;

        if(head<tail && dat[q[head]].h>=dat[i].h*) cnt[i]++;

        q[tail++]=i;

    }

    head=;

    tail=;

    for(int i=n-;i>=;i--)

    {

        while(head<tail && dat[q[head]].x-dat[i].x>d) head++;

        while(head<tail && dat[q[tail-]].h<=dat[i].h) tail--;

        if(head<tail && dat[q[head]].h>=dat[i].h*) cnt[i]++;

        q[tail++]=i;

    }

    for(int i=;i<n;i++)

    {

        if(cnt[i]==) ans++;

    }

}

void print()

{

    cout<<ans<<endl;

}

int main()

{

    read();

    solve();

    print();

}

巴特西

BZOJ 3314 [Usaco2013 Nov]Crowded Cows：单调队列

最新文章

热门文章