问题 : 紧张的考试周【区间覆盖的时间优化】【二分】

    xiaoxiao2021-03-25  34

    问题 : 紧张的考试周

    时间限制: 1 Sec   内存限制: 128 MB  

    题目描述

    马上要到考试周了,王炸发现自己平时光顾着去网吧学ACM了,功课还真没怎么复习。抛开数据结构这种送分的课程,还有一些例如大物、概率论这种费时费力的课程。王炸决定花上一些时间开始复习了。

    根据考试安排,王炸发现自己有n门功课需要复习,对于每门功课,给出Si、Li(1 ≤ i ≤ n),分别表示复习该门课程的开始时间以及持续时间。但是王炸发现这些复习的时间段有重合部分,也就是说只凭自己本身是不能复习完所有功课的,但是这难不倒王炸,他从师父那里学到了一招————奥义·影分身,王炸可以让自己的分身和自己同时复习。但是释放影分身需要消耗相当大的能量,所以他想尽量少的释放影分身。

    现在他请你帮他算一下他至少需要多少影分身才能复习完所有课程。

    输入

    第一行一个整数T(1 ≤ T ≤ 50)表示一共T组数据

    每一组数据的第一行有一个正整数n(1 ≤ n ≤ 10000),表示需要复习功课的数量。

    接下来n行,每行两个数Si和Li(1 ≤ Si、Li ≤ 10^7),表示的意义如题目描述所示。

    输出

    对于每组数据输出一个整数,表示最少需要的影分身的数量。

    样例输入

    2 2 1 2 2 1 4 5 2 3 6 1 2 1 3

    样例输出

    1 1

    提示

    对于样例1,因为第2个时间点有重合,所以需要派出一个影分身去复习,所以应该输出1。

    对于样例2,王炸自己学习功课3和2,派出一个影分身学习功课4和1,所以应该输出1

    补充i点知识先  /*  upper_bound() #include <iostream> #include <algorithm>//必须包含的头文件 using namespace std; int main(){  int point[10] = {1,3,7,7,9};  int tmp = upper_bound(point, point + 5, 7) - point;//按从小到大,7最多能插入数组point的哪个位置  printf("%d\n",tmp);  tmp = lower_bound(point, point + 5, 7) - point;按从小到大,7最少能插入数组point的哪个位置  printf("%d\n",tmp);  return 0; } output: 4

    2*/

    思路: 可以看出来 ,就是区间覆盖问题,但是一看时间都凌乱了。。 问了大神才 有的优化时间后的代码 

      每有一个开始,个数就要+1,每完成一件事情,个数就要-1;  所以要是在一个区间里一直有加的个数大于减的个数,就表明是 有重叠了、、、 在这期间一直更新max_num的个数就可以了。。。

    代码

    #include<string.h> #include<stdio.h> #include<algorithm> #include<math.h> #include<queue> #include<stack> #define inf 0x3f3f3f #define M 10000*2+10 #define LL long long using namespace std; int a[M]; int b[M]; int cmp(int x,int y) { return x<y; } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int time; scanf("%d%d",&a[i],&time); // 记录 开始的点 b[i]=a[i]+time; // 记录 结束的点 } sort(a,a+n,cmp); //排序 sort(b,b+n,cmp); int max_num=-1; for(int i=0;i<n;) // 核心 { int k=upper_bound(a,a+n,a[i])-a; // 记录 a[i]这个点之前有几个开始的点 有几个开始加几 int l=upper_bound(b,b+n,a[i])-b-1;//a[i] 这个点之前有几个结束的点 有几个结束的点,就减几 i=k; if(max_num<k-l-1) max_num=k-l-1; } printf("%d\n",max_num-1); } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-50287.html

    最新回复(0)