时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32M,其他语言64M
一年一度的快手运动会又要开始了,同学们终于有一天可以离开鼠标键盘显示器,全身心的投入到各种体育项目中。UED设计师小红虽然没有参加体育项目,但她的责任重大,因为她是拉拉队的队长,她需要在每个项目中为参赛的同学们加油助威。
因为运动会的项目众多,很多项目在同一时间会同时进行着。作为拉拉队长,小红需要遵守以下规则:
不能同时给多个体育项目加油助威
给每个体育项目加油的时长必须超过项目时长的一半,每个体育项目只能加油一次
体育项目的开始和结束时间都是整点,如果项目进行到一半想要离开,也只能选择整点离开
不考虑往返于各个体育项目比赛场地中花费的时间
请帮小红设计一个算法,在已知所有体育项目日程的前提下,计算是否能在每个体育项目中为参赛的同学们加油。
说明:
如果体育项目时长为2,超过时长的一半为2;
如果体育项目时长为3,超过时长的一半为2;
如果体育项目时长为4,超过时长的一半为3;
输入描述:
输入包括1+N行 第一行输入一个整数N, 1 <= N <= 10,表示今天要参加多少个讨论会 后续N行,每行输入开始和结束时间,均为整数,用空格分隔,0 <= startTime < endTime <= 24
输出描述:
输出包括一行 如果小红能够参加全部讨论会,返回1 如果小红不能够参加全部讨论会,返回-1
输入例子1:
3
3 10
1 5
4 6
输出例子1:
1
题解:
在该题中,要对所有时间段按中点进行排序,在该题中,对与时间为大于一半才能算参加完这个节目,所以对于要进入的下一个题目,除了判断当前中点是否在下一段的范围内,还要判断当前的中点是否在下一段的一半之前。
用pair存储时间段,定义一个比较函数或者是lambda函数,用来进行排序。
除此之外,如何判断当前的中点是否在下一段的时间段的前半段内,对于时间段是奇数还是偶数是不同的。例如[3,10]的前半段,小于7即可。对于[1,5]的前半段要小于小于3,与本体的定义有关,所以在判断是否是位于前半段时,运用了求和和求商的技巧。
if(mid < record[i+1].first || mid > record[i+1].second || mid >= record[i+1].first + (record[i+1].second - record[i+1].first)/2 + (record[i+1].second - record[i+1].first)%2)
仔细体会如何确定在前半段。