算法分析

有一本书总共有N页,现在缺少一页,给出了M条线索,起始页是S,结束页E,假如在S-E之间状态为1,在S-E之外用0标识,找出缺少页数。

测试用例
第一行输入用例数,
第二行输入总页数,线索数
第三行输入起始页,结束页,状态

输出为:#用例序号  缺失页码

例:
输入
3
10 2
1 5 0
7 10 0
40 3
10 30 1
20 40 0
1 18 0
50 4
8 50 0
8 50 0
1 8 1
1 6 0


输出:
#1 6
#2 18
#3 7


#笔试题目##面经##悬赏#
全部评论
就是找区间的差集。如果给出的区间有解的话,你就是要从1-N的总区间,与M条线索中的区间做差集: 1、先把线索排序,线索为1的放前面 总区间就从1-N变成了线索为1的S-E2、用区间去对线索为0的做差集 循环做差集,最后剩下的数字就是缺失的页数。 第二个用例的答案应该错了,答案应该是19
点赞 回复
分享
发布于 2019-04-25 09:14

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务