，关于csdn的英雄会的一个题目，微软出的那个
求助，关于****的英雄会的一个题目，微软出的那个。
http://hero.****.net/Question/Details?ID=624&ExamID=619&from=4
这个题目我用c++写的，给出的用例我跑了ok的，然后我提交了，告诉我运行结束，结果和期望不符，失败了。
本来是闲的练练手，结果被搞的郁闷了，就想一探究竟。唉。
发帖的目的就是想知道，亲，怎么知道他的test case？
比赛还没有结束吧，所以不好贴全部的代码，过几天贴出来吧。
------解决方案--------------------
有M个机器，其中，所述第i个机器有次芯（ⅰ从1开始）。在每台机器上，芯结构中的一行。
有以下类型的服务q查询：
1，问对k内核。我们必须找到与第一台机器（
至少指数），使得它有K个连续的无芯并为它们分配
给客户。如果有一个解决方案，返回结果（M，C），其中m
被机器和c的索引是第一核心的分配索引
在机器上。否则，返回（-1，-1）。一旦内核被分配
它们不能被使用，直至它们被释放。
2，释放的核
分配的所述第一类型的一个查询中。我们保证
所述第一类型的第a个查询存在与每个查询被释放至多
一次。如果相应的查询没有一个解决方案，你应该只
忽视它。
[输入参数]
第一行给出了一个整数T，测试用例的数量。
为
每个测试例中，第一行给出了M和Q，则M线跟随，每
其中包含一个数字，指示次为第i行。对于
接下来的Q行，他们每个人给出的查询。
1，A K。对应于查询的第一类型，k是请求的核心数。
2，F A。对应于第二类型的查询，一个指示第一类型的一个查询。
所有的数字都是整数。
[输出规格]
为
每个测试案例，第一输出线在此格式“案例＃我：”（不
引号），其中i是案件编号，从1开始，之后，
输出结果为1型的每个查询，无论是“MC”（不带引号），如果
有解决的查询，或“-1 -1”（不带引号），如果没有
解决方案找到。
[限制]
1<= T<=20
1<= M<=100000
1 <=次<=128
1<= Q<=百万
1<= K<=128
1<= A <= Q
类型1的查询的数量是相同的类型2。
------解决方案--------------------
这题的难点应该是如何排序，每次分配时最多需要访问128*10000个节点，所以遍历搜索不可取，必须排序。这里有3个关键字段：机器号（1-10000），内核号（1-128），连续空闲数量（1-128），而每次给出的搜索条件只有连续空闲数量（比如A 10 -- 分配连续10个core），必须找出匹配的最小机器号+最小内核号，这里的最大问题是如何排序，一般思考总是按搜索条件排序，比如用最大空闲数量+机器号+内核号这样的顺序排序，但是按题目要求这样排序并不能找到合适结果，因为比如你需要分配连续10个core，而满足条件的可能有第300号机器第7内核开始有10个core空闲，第5000机器第50内核开始有10个空闲，第156号机器第3内核开始有100个空闲，按题目要求，匹配的是（156，3）而不是排序之后得到的结果（300，7），而如果用机器号+空闲数+内核号排序，因为输入条件只有一个空闲数，所以还是必须遍历搜索。
本帖最后由 ztz0223 于 2014-07-23 14:31:22 编辑
题目链接：http://hero.****.net/Question/Details?ID=624&ExamID=619&from=4
这个题目我用c++写的，给出的用例我跑了ok的，然后我提交了，告诉我运行结束，结果和期望不符，失败了。
本来是闲的练练手，结果被搞的郁闷了，就想一探究竟。唉。
发帖的目的就是想知道，亲，怎么知道他的test case？
比赛还没有结束吧，所以不好贴全部的代码，过几天贴出来吧。
------解决方案--------------------
有M个机器，其中，所述第i个机器有次芯（ⅰ从1开始）。在每台机器上，芯结构中的一行。
有以下类型的服务q查询：
1，问对k内核。我们必须找到与第一台机器（
至少指数），使得它有K个连续的无芯并为它们分配
给客户。如果有一个解决方案，返回结果（M，C），其中m
被机器和c的索引是第一核心的分配索引
在机器上。否则，返回（-1，-1）。一旦内核被分配
它们不能被使用，直至它们被释放。
2，释放的核
分配的所述第一类型的一个查询中。我们保证
所述第一类型的第a个查询存在与每个查询被释放至多
一次。如果相应的查询没有一个解决方案，你应该只
忽视它。
[输入参数]
第一行给出了一个整数T，测试用例的数量。
为
每个测试例中，第一行给出了M和Q，则M线跟随，每
其中包含一个数字，指示次为第i行。对于
接下来的Q行，他们每个人给出的查询。
1，A K。对应于查询的第一类型，k是请求的核心数。
2，F A。对应于第二类型的查询，一个指示第一类型的一个查询。
所有的数字都是整数。
[输出规格]
为
每个测试案例，第一输出线在此格式“案例＃我：”（不
引号），其中i是案件编号，从1开始，之后，
输出结果为1型的每个查询，无论是“MC”（不带引号），如果
有解决的查询，或“-1 -1”（不带引号），如果没有
解决方案找到。
[限制]
1<= T<=20
1<= M<=100000
1 <=次<=128
1<= Q<=百万
1<= K<=128
1<= A <= Q
类型1的查询的数量是相同的类型2。
------解决方案--------------------
这题的难点应该是如何排序，每次分配时最多需要访问128*10000个节点，所以遍历搜索不可取，必须排序。这里有3个关键字段：机器号（1-10000），内核号（1-128），连续空闲数量（1-128），而每次给出的搜索条件只有连续空闲数量（比如A 10 -- 分配连续10个core），必须找出匹配的最小机器号+最小内核号，这里的最大问题是如何排序，一般思考总是按搜索条件排序，比如用最大空闲数量+机器号+内核号这样的顺序排序，但是按题目要求这样排序并不能找到合适结果，因为比如你需要分配连续10个core，而满足条件的可能有第300号机器第7内核开始有10个core空闲，第5000机器第50内核开始有10个空闲，第156号机器第3内核开始有100个空闲，按题目要求，匹配的是（156，3）而不是排序之后得到的结果（300，7），而如果用机器号+空闲数+内核号排序，因为输入条件只有一个空闲数，所以还是必须遍历搜索。