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

川长思鸟来 2024-02-19 19:46 6阅读 0赞

### 1461: 饥饿的牛 ###

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

### 题目描述 ###

牛在饲料槽前排好了队。饲料槽依次用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行，每行两个整数，表示一个区间，较小的端点在前面。

### 输出 ###

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

### 样例输入 ###

### 样例输出 ###

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

#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;
    }

加油，ヾ(◍°∇°◍)ﾉﾞ

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1461
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1461
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1461