2017年西南民族大学网络赛之免费WIFI

矫情吗；* 2022-06-02 04:20 156阅读 0赞

/*
    题目描述
    TRDD开了一家免费WiFi体验店， 所有人都可以免费连接WiFi， 只有一个条件， 你要提前一天预约。今天，TRDD收到了n(1 <= n <=1000)个人的预约， 每个人有一个时间段[L, R] (1 <= L <= R <= 5000)表示这个人预约连接WiFi从L时刻到R时刻。 但是市面上只有一种路由器， 这种路由器单台最多能同时连接m(n <= 100)台设备， TRDD想要知道最少使用多少台路由器就能保证明天每个人都能连上WiFi。
    输入描述:
    第一行包含两个数n(1 <= n <=1000), m (1 <= m <= 100)表示今天有n个人预约， 以及路由单台最大连接个数m。
    之后有n行， 第i行有两个数字  [L, R] (1 <= L <= R <= 5000) 表示第i个人预约连接WiFi的时间是从L到R。
    输出描述:
    输出一个数字表示TRDD最少需要开启的路由器的个数。
    示例1
    输入
    
    4 1
    1 5
    2 7
    3 4
    6 9
    输出
    
    3
    */
    #include<bits/stdc++.h>
    #include<queue>
    using namespace std;
    struct A{
    	int a,b;
    }f[1001];
    bool cmp(A x,A y){
    	if(x.a==y.a)
    		return x.b<y.b;
    	return x.a<y.a;
    }
    int main()
    {
    	int n,m;
    	priority_queue<int,vector<int>,greater<int> > q;
    	while(~scanf("%d %d",&n,&m)){
    		for(int i=0;i<n;i++){
    			scanf("%d %d",&f[i].a,&f[i].b);
    		}
    		//先按照开始时间从小到大排序，如果开始时间相等，就按照结束时间从小到大排序
    		sort(f,f+n,cmp);
    		//先把排好序的前m个的结束时间放进队列
    		for (int i = 0; i < m; i++)
    			q.push(f[i].b);
    		int j=m;
    		int count=1;//一个是肯定要的
    		while(j<n){
    			int temp=q.top();
    			//如果前一个的结束时间小于下一个的开始时间,
    			//（这里只能是小于，不能是小于等于,我掉坑里了）
    			//就把下一个入队列，前一个出队列，相当于上一个连WIFI的人走了,而下一个可以来了；
    			if(temp<f[j].a){
    				q.pop();
    				q.push(f[j].b);
    				j++;
    			}
    			/*
    				否则说明路由器不够,需要加一个新的路由器;
    				加了一个新的路由器,当然是尽量让最多的人用
    				所以能够连多少个就连多少个;
    			*/
    			else{
    				count++;
    				for(int i=0;i<m;i++){
    					q.push(f[j++].b);
    				}
    			}
    		}
    		printf("%d\n", count);
    	}
    	return 0;
    }