UC知道一道NOIP模拟题
来源：百度知道 编辑：UC知道 时间：2024/06/23 05:11:24
房间安排
程序名：room.pas/c/cpp
文件输入/输出：room.in/out
某旅游地一个旅馆某一天接到了大量的客房定单，每张定单的内容包括房间数、开始使用时间和使用的天数。为了便于宾馆管理和接待尽量多的旅客，宾馆经理不得不对这些定单进行安排，安排目的是用尽量少的房间来满足这些定单，以便空出更多房间用于安排其他流动客户。宾馆经理花了几天时间来处理，但每次处理之后，他总觉得他的安排不是最最好的。请你帮助宾馆经理处理这个问题。
为了便于计算，我们假设：
安排房间的这一天所有的房间都是空的。
宾馆的房间数是可以满足定单要求的，即假设房间数是无限的。
每张订单被简化为房间数、开始时间和天数，开始时间为一个整数，表示距离现在的第几天。例如，定单如为2、7、4。表示旅客要求为从第7天开始的4天时间里使用2个房间（第7，8，9，10天这4天里用2个房间）。
旅客一旦被安排在某个房间，在他的预定时间里是不允许换房间的。
你的任务就是：帮助宾馆经理对这些订单进行有效的安排，使的为安排这些订单而使用的房间数最少。
输入
第1行为正整数N，N为订单数（N≤10000）
第2行到N+1行的每一行为一张订单，每行有3个正整数S、K和T，其中S为房间数、K为开始时间，T为天数。
注：1≤S≤9，K和T在[1，60000]之间
输出
为最少的房间数。
输入示例
3
1 2 4
4 1 3
2 4 6
输出示例
5
这道题谁会？给个c++代码
程序名：room.pas/c/cpp
文件输入/输出：room.in/out
某旅游地一个旅馆某一天接到了大量的客房定单，每张定单的内容包括房间数、开始使用时间和使用的天数。为了便于宾馆管理和接待尽量多的旅客，宾馆经理不得不对这些定单进行安排，安排目的是用尽量少的房间来满足这些定单，以便空出更多房间用于安排其他流动客户。宾馆经理花了几天时间来处理，但每次处理之后，他总觉得他的安排不是最最好的。请你帮助宾馆经理处理这个问题。
为了便于计算，我们假设：
安排房间的这一天所有的房间都是空的。
宾馆的房间数是可以满足定单要求的，即假设房间数是无限的。
每张订单被简化为房间数、开始时间和天数，开始时间为一个整数，表示距离现在的第几天。例如，定单如为2、7、4。表示旅客要求为从第7天开始的4天时间里使用2个房间（第7，8，9，10天这4天里用2个房间）。
旅客一旦被安排在某个房间，在他的预定时间里是不允许换房间的。
你的任务就是：帮助宾馆经理对这些订单进行有效的安排，使的为安排这些订单而使用的房间数最少。
输入
第1行为正整数N，N为订单数（N≤10000）
第2行到N+1行的每一行为一张订单，每行有3个正整数S、K和T，其中S为房间数、K为开始时间，T为天数。
注：1≤S≤9，K和T在[1，60000]之间
输出
为最少的房间数。
输入示例
3
1 2 4
4 1 3
2 4 6
输出示例
5
这道题谁会？给个c++代码
先将 k_i t_i 这 2×n 个数字排序
用n记录当前已开房间数
用m记录n个已开房间中的空房间数
从小到大，扫排好序的2×n个数字，
遇k_i 减空房，或开新房间
遇t_i 将房间纳入空房
排序效率 O(nlogn) 扫的效率 O(n)
离散化+模拟
额，就是排序+模拟