首页 > 代码库 > bnu-44582

bnu-44582

昨天北师大新生赛的题,本弱做一做。。。

贪心题,按照结束时间排序进行贪心。

http://www.bnuoj.com/v3/problem_show.php?pid=44582


MLX的疯狂睡眠

Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld      Java class name: Main
Prev 
Submit Status Statistics Discuss
 Next
Type: 
None
     

    在一个寝室中,有早上6点多起床跑自习室或者图书馆,晚上11点多回寝室洗洗直接睡觉的神牛(真是神一般的存在);也有早上11点多起来直接吃饭,下午玩一会累了又sleep的睡神;也有白天一直陪妹子,大晚上和寝室程序猴子作伴的泡神;也有早上不知道何时起,从下午到第二天早些时候(确实早啊!)一直code的神码手····那么现在问题来了,寝室本来是一个非常友好的team,但是为了证明自己的睡眠行为是大学最完美的,他们决定来一场惊天地的辩论····MLX作为寝室的一员,突然做出一个疯狂的决定:统计出寝室每一个成员的睡眠时间段(每一个成员可能有多个睡眠时间段),然后将亲自实践每一个成员睡眠方式,然后再决定谁的更好。聪明的您可能会想这样一个问题:如果MLX从进入一个睡眠段开始到结束中途不醒,MLX那一天最多能睡多少次?

    现在将问题进一步抽象为:一天内有n个睡眠区间,每一个睡眠区间分别为距离当天0点的第Si秒开始,第Ti秒结束。对于每一次睡眠,MLX都可以参与或者不参与,如果选择了,那么MLX就必须将本次睡眠进行到底。此外,参与睡眠的时间不能重复(即使是刚开始的瞬间和结束的瞬间的重复也是不允许的),请问MLX最多能参与多少次睡眠?

    Input

    第一行输入T,表示T组测试数据。

    每一组的第一行输入n,表示有n个睡眠区间(1<= n <=10^5 )

    接下来n行,每一行输入两个整数Si,Ti(空格隔开),表示睡眠区间的开始和结束时间(1<= Si< Ti< 24*3600)

    Output

    MLX最多参与的睡眠次数

    Sample Input

    1
    5
    1 3
    2 5
    4 7
    6 9
    8 10

    Sample Output

    3

    Hint

    参与的睡眠编号依次是(1,3,5)


    #include<stdio.h>
    #include<iostream>
    #include<math.h>
    #include<stdlib.h>
    #include<ctype.h>
    #include<algorithm>
    #include<vector>
    #include<string.h>
    #include<queue>
    #include<stack>
    #include<set>
    #include<map>
    #include<sstream>
    #include<time.h>
    #include<utility>
    #include<malloc.h>
    
    using namespace std;
    
    int n;
    
    struct Q
    {
    	int s;
    	int e;
    }p[100010];
    
    bool cmp(Q a, Q b)
    {
    	return a.e < b.e;
    }
    
    int cases;
    
    int main()
    {
    	cin >> cases;
    
    	while (cases--)
    	{
    		cin >> n;
    		for (int i = 1; i <= n; i++)
    			cin >> p[i].s >> p[i].e;
    
    		sort(p+1,p+1+n,cmp);
    
    		int ans = 1;
    		int t = p[1].e;
    
    		for (int i = 2; i <= n; i++)
    		{
    			if (t < p[i].s)
    			{
    				ans++; 
    				t = p[i].e;
    			}
    		}
    		cout << ans << endl;
    	}
    	return 0;
    }


    bnu-44582