洛谷P7113 [NOIP2020] 排水系统

洛谷P7113 [NOIP2020] 排水系统是一道关于城市排水系统的问题，题目描述了城市排水系统是一个n个节点的DAG(有向无环)图，有m个污水接收口且每个污水接收口有1吨的水，放水过程中会平均分给子节点，没有子节点的水管就是最终排水口,最后按编号顺序输出每个最终排水点的污水(以分数形式)。同时，题目提供了两种解法，一种是使用数组模拟，另一种是使用优先队列模拟。

解法一使用数组模拟，首先读入n和m，然后读入每个污水接收口的水量，接着使用t表示下一个排队的同学的位置，res表示正在节水的m个同学，那么当前在接水的第一个同学就是t-m。为了让所有学生接完水，t需要遍历到n+m。遍历水龙头，按秒遍历，如果某个同学接水量变为0的时候，说明这位同学接完了水，将下一位同学放在这个水龙头即可。最后输出res即可。

解法二使用优先队列模拟，首先读入n和m，然后读入每个污水接收口的水量，接着使用一个优先队列存储每个污水接收口的编号和水量，按照水量从小到大排序。然后使用一个循环，每次取出队首元素，将其水量平均分给子节点，如果子节点的水量变为0，则将其加入队列中。直到队列为空，输出每个最终排水点的污水即可。

相关问题

洛谷1093 [NOIP2007 普及组] 奖学金

洛谷1093 [NOIP2007 普及组] 奖学金是一道算法题，出自国内在线编程平台洛谷的题库。这道题目是2007年全国信息学奥林匹克普及组的一道题目，也是NOIP（全国青少年信息学奥林匹克竞赛）的一部分。

题目描述如下：给定N个申请者的学业成绩、面试成绩、论文成绩和奖金数额，按照一定的规则来确定奖学金的分配。规则如下：
1. 学业成绩高于80分且有论文成绩的申请者可获得奖金8000元；
2. 学业成绩高于85分且面试成绩高于80分的申请者可获得奖金4000元；
3. 学业成绩高于90分的申请者可获得奖金2000元；
4. 学业成绩高于85分且有奖金的申请者可获得奖金1000元；
5. 面试成绩高于80分且有论文成绩的申请者可获得奖金850元。

要求编写一个程序，根据给定的N个申请者的相关信息，计算出总共发放的奖金数额。

这道题目主要考察对条件判断和基本计算的理解和运用。你可以通过编写一个程序来解决这个问题，根据每个申请者的成绩和条件进行判断，然后计算出总共发放的奖金数额。希望能对你有所帮助！

洛谷的[NOIP1999 普及组] 导弹拦截

洛谷的[NOIP1999 普及组] 导弹拦截 是一道程序设计题。

题目大意是这样的：有一个国家发射了若干枚导弹，它们从不同的高度飞行，你有若干个导弹拦截器可以用来摧毁导弹。每个导弹拦截器的射程是固定的，并且它可以在任意高度摧毁导弹。你的任务是写一个程序，计算出使用最少的导弹拦截器就可以摧毁所有的导弹。

输入格式：

第一行包含两个整数 N 和 H，表示导弹的数量和天空的高度。

接下来 N 行，每行包含一个整数，表示导弹的飞行高度。

最后一行包含一个整数 R，表示导弹拦截器的射程。

输出格式：

输出一个整数，表示最少需要的导弹拦截器数量。

输入输出样例

输入样例#1：

5 1000
600
800
1200
1400
1600
200

输出样例#1：

3

数据范围：

1≤N≤100,
1≤H≤10000,
1≤高度≤10000,
1≤R≤1000

解题思路：

这是一道贪心题。我们可以将导弹按照飞行高度从小到大排序，然后从第一枚导弹开始，逐个摧毁