NOIP2010第三题|NOIP2010第三题 ---接水问题 NOIP2010第三题---接水问题

题目：
学校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。
现在有 n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 1 到 n 编号，i 号同学的接水量为 wi。接水开始时，1 到 m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学 j 完成其接水量要求 wj 后，下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。亦即，j 同学第 x 秒结束时完成接水，则 k 同学第 x+1 秒立刻开始接水。若当前接水人数 n’不足 m，则只有 n’个龙头供水，其他 m - n’个龙头关闭。
现在给出 n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
【数据范围】
1≤n≤10000，1≤m≤100 且 m≤n；
1≤wi≤100。
输入要求：
请输入两个整数：2 个整数 n 和 m，用一个空格隔开，分别表示接水人数和龙头个数。
再请输入n个整数：n 个整数 w1、w2、…、wn，每两个整数之间用一个空格隔开，wi 表示 i 号同学的接水量。
输出界面：
输出只有一行，1 个整数，表示接水所需的总时间。
如：
输入：
5 3
4 4 1 2 1
输出：
4
再如：
8 4
71 87 32 70 93 80 76
输出：
163
解题思路：
首先一定要审清题，接水顺序是固定好的。我最开始犯了这个错误，想着既然时间最短，就把所有接水时间先排个序再算，结果答案和标准答案大相径庭。
例如输入为：
5 3
4 4 1 2 1
人数小于水龙头数时，所用时间应该是所有人接水时间的最大值；
人数大于水龙头数时，最开始3个水龙头下的待接水量应该是：
4 4 1（等待接水的人：2 1）
第一个接完水的人是接水量为1的那个人，那么此时水龙头下的待接水量应该是：
3 3 0
由于不管哪个人接完水，下一个人都要立即接替，所以在这瞬间，水龙头下的待接水量变为：
3 3 2（等待接水的人：1）
那么接下来这一组，最先接完水的是接水量为2的那个人，此时水龙头下的待接水量应该是：
1 1 0
瞬间之后，水龙头下的待接水量变为：
1 1 1（没有等待接水的人了）
这些人中最大的接水量是1.
所以，所用的所有时间加起来为1+2+1=4.
这个是基本方法，不是很简洁。不过时间复杂度O(m*n)，一百万级，应该足够了，不会超时。
public class test37 {

public static int[] minute = new int[200]; public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int m = s.nextInt(); for(int i = 0; i < n; i ++) minute[i] = s.nextInt(); int x = getNumber(n, m); System.out.println(x); s.close(); }public static int getNumber(int n, int m) { if(n <= m) return minute[getMaxIndex(minute, n)]; int[] a = new int[m]; //初始化 for(int i = 0; i < m; i ++) a[i] = minute[i]; int sum = 0, t, tmp; for(int i = m; i < n; i ++) { t = getMinIndex(a, m); sum += a[t]; tmp = a[t]; for(int j = 0; j < m; j ++) a[j] -= tmp; a[t] = minute[i]; } sum += getMaxIndex(a, m); return sum; }public static int getMaxIndex(int[] a, int n) { int max = -9999; for(int i = 0; i < n; i ++) if(a[i] > max) max = a[i]; return max; }public static int getMinIndex(int[] a, int n) { int min = 9999, t = -1; for(int i = 0; i < n; i ++) if(a[i] < min) { min = a[i]; t = i; } return t; }

【NOIP2010第三题|NOIP2010第三题 ---接水问题】}