1461: 饥饿的牛贪心 +优先队列-蒲公英云

1461: 饥饿的牛贪心 +优先队列

1461: 饥饿的牛

时间限制: 1 Sec 内存限制: 128 MB
提交: 25 解决: 14
您该题的状态：已完成
[提交][状态][讨论版]

题目描述

牛在饲料槽前排好了队。饲料槽依次用1到N(1<=N<=2000)编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。

约翰提供B个区间的清单。一个区间是一对整数start-end,1<=start<=end<=N，表示一些连续的饲料槽，比如1-3,7-8,3-4等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。

当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多的东西。

在上面的例子中，1-3和3-4是重叠的；聪明的牛选择{1-3，7-8}，这样可以吃到5个槽里的东西。

输入

第一行，整数B(1<=B<=1000)

第2到B+1行，每行两个整数，表示一个区间，较小的端点在前面。

输出

仅一个整数，表示最多能吃到多少个槽里的食物。

样例输入

<span style="color:black">3
1 3
7 8
3 4
</span>

样例输出

<span style="color:black">5
</span>

优先队列对结构体进行排列，让末端点从小到大排列，在设置一个标志位，记录上一个区间的末端点，如果大于这个标志，则进行累加。不大于的话，扔掉。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef struct 
{
    int former,later;
}node;
bool operator <(const node &a,const node &b)
{
    return a.later>b.later;
}
int main()
{
    priority_queue<node> q;
    node s[1001];
    int i,j,n;
    int sum=0,last=-1;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>s[i].former>>s[i].later;
        q.push(s[i]);
    }
    while(!q.empty())
    {
        node d=q.top();
        q.pop();
        if(d.former>last)
        {
            sum+=(d.later-d.former+1);
            last=d.later;
        }
    }
    cout<<sum<<endl;
    return 0;
}