牛客练习赛51 t4 羊吃草 题解

题意分析

• 先给出n和q，n代表羊的数量，q代表下面给出的区间数量。
• 然后两行代表每只羊吃草的能力范围，
  • 第一行代表第i只羊吃草范围的能力极限左端点，
  • 第二行代表第i只羊吃草范围的能力极限右端点，
• 第三行开始q行代表要查询的区间，每次查询一个区间，问你有多少头羊能吃到草。
  • 每行给出和，问你在Left到Right组成的区间内，最多能有多少头羊吃到草。
  • 每头羊只需要一个点的空间吃草。
• 例如在1~5这个区间内查询，而羊有（1至1）、（1至2）、（1至3）、（1至4）、（1至5）的，则5头羊分别可以被安排到位置1、2、3、4、5吃草。答案是5。如果6头羊，答案也不会变。

解题思路

• 贪心+堆，

  • 为什么想到贪心？

    首先我们不难想到，“要让这个区间里面更多的羊吃到草”，那不就是贪心了吗？

  • 为什么想到堆？

    ……我们对于每个点能不能让羊吃到草，应该是枚举这个区间。枚举这个区间，位置在从左往右移动的时候，当前点能够匹配的区间，一定要保证左端点小于等于自己，右端点大于等于自己。

    所以……

参考程序

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
struct OneSheep
{
    int l,r;
} a[405];
bool cmp(OneSheep a,OneSheep b)
{
    return a.l<b.l;
}
int n,Query,ans;
priority_queue<int,vector<int>,greater<int> > pq;
int main()
{
    scanf("%d%d",&n,&Query);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].l);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].r);
    sort(a+1,a+1+n,cmp);
    int l,r,i;
    while(Query--)
        {
            scanf("%d%d",&l,&r);
            for(i=1;i<=n;i++)    
                if(a[i].l<l&&a[i].r>=l)
                    pq.push(a[i].r);
                else
                    if(a[i].l>=l)
                        break;

            for(;l<=r;l++)
                {
                    while(!pq.empty()&&pq.top()<l)
                        pq.pop();

                    while(i<=n&&a[i].l<=l)
                        {
                            pq.push(a[i].r);
                            i++;
                        }
                    if(!pq.empty())
                        {
                            ans++;
                            pq.pop();
                        }
                }
            while(!pq.empty())
                pq.pop();

            printf("%d\n",ans);
            ans=0;
        }
    return 0;
}