制作一个网站首页,网站建设pad版本是什么,常平东莞网站设计,软件培训方案题目不少于5个字#xff0c;所以整了个括号凑字数 首先我想到的是用一个数组来记录每一秒的在线人数
但是即使是short类型#xff08;2字节#xff09;#xff0c;也会用到60 * 60 * 24 * 30 * 12 * 60 * 2 / 1024 / 1024 3,559.5703125 MB
而题目上限是256MB#xff0…
题目不少于5个字所以整了个括号凑字数 首先我想到的是用一个数组来记录每一秒的在线人数
但是即使是short类型2字节也会用到60 * 60 * 24 * 30 * 12 * 60 * 2 / 1024 / 1024 3,559.5703125 MB
而题目上限是256MB超了虽然时间复杂度是On 第二个想到的是一个一个处理数据用一个数组记录目前的时间区间如果新数据没有和目前的时间区间重合就新创建一个如果重合该时间区间就缩小到重合部分而该时间区间的重合数加一
这个方法的时间复杂度最低是On最高是On * (n 1) / 2)
但是这个方法不可行因为记录的时间区间是不断缩小的如果有新的时间区间和旧的记录的较大的时间区间重合的话之前的重合数就没有记录下来
如[1,5), [4,5), [1,2), [1,2)答案是3而按这个方法计算是2 所以每一个时间区间都要比较
设置一个临时的时间区间一一等于每一个时间区间然后在每一轮对所有的时间区间进行比较
而且不断缩小到重合部分记录重合数对所有的重合数取最大值就是答案了
时间复杂度是On ^ 2 代码如下
#includestdio.h
struct Time{int A;int B;
}time[1000];
int jud(int A1, int B1, int A2, int B2);int main(void)
{int n, maxn 0;scanf(%d, n);for(int i 0; i n; i)scanf(%d%d, time[i].A, time[i].B);for(int i 0; i n; i){struct Time tmp;int count 0;tmp.A time[i].A, tmp.B time[i].B;for(int j 0; j n; j)if(jud(time[j].A, time[j].B, tmp.A, tmp.B)){tmp.A (tmp.A time[j].A) ? tmp.A : time[j].A;tmp.B (tmp.B time[j].B) ? tmp.B : time[j].B;count;}maxn (maxn count) ? maxn : count;}printf(%d, maxn);return 0;
}
int jud(int A1, int B1, int A2, int B2)
{if(B1 A2 || A1 B2)return 0;return 1;
}
