题解 | #[NOIP2010]接水问题#

考察重点：数组，排序

首先根据题意，有n名学生要用m个水龙头来接水，要求我们找出所有学生都接完水需要花的时间。

很明显，重点不在于所有人一起花了多久，我们需要“反过来想”（逆向思考）：找出所有同学花的时间，其实就是找出哪个水龙头用水花的总时间最长（比如1号水龙头总共用了wi = 114来装水，2号用了wj = 514来装水，那最终花的总时间只取决于耗时最多的那个(木桶效应)，所以总共花了514秒，）也就是说，重点不在于下一个是谁来装水，而是下一个轮到哪一个水龙头来放水给学生用。关键在于找出那个耗时最多的水龙头，它的总用时即为所有学生需要花的时间。

由于结果跟n, m的对应大小有关，我们需要分别讨论：

1. 当前接水人数n不足m（即n<=m）

• 这种情况下，m个水龙头是够用的，那就一个萝卜一个坑，有多少个学生要接就给多少水龙头，一一对应找出耗时最多的就好了

	for (int i = 0; i < m; i++) {
		location[i] = arr[i];		//最简单の情况
	}

2. 当前接水人数n比m多

• 接下来重点来说说这个情况

• 我们模拟一下过程，来找找其中的规律：

  --> 以样例1为例，

  n=5 , m=3

  w = 4 4 1 2 1

  这里前三个先去装水，后面两个（n-m）等前面的装完，过了1s后，第三个水龙头空出，换下一个人（此时前两个还要装3s），再过2s后, 等最后的人装完，恰好总共花了4s所有人装完。

  可以看到，下一个人要装去装水的地方取决于上一个谁先装完，即前一种情况是谁装水花的总时长最短，这样才会空出来位置，下一个才能马上接上去装水。至于跟其他人就没关系了———因为他们选中了就不会再换一个水龙头来装水，直到自己的那份装完为止。

  （比如本题用例二，如果23，71，87，32为一组，那么等到70接进去，是23的那边先装完，那么70就会选择1号来装水，此时1号后面就一共要装 23+70=93，接着轮到93，那么就要在93，71， 87， 32之间选，这时，就轮到4号水龙头那边同学先装完水，所以93会选择4号，4号的总用量也由此变为 32+93=125，之后 71+80=151（第三轮2号最小，80选择）， 87+76=163（最后一轮3号最小，76选择），最终情况变为：93， 151， 163（耗时最多）， 125， 所以输出为163。搞定。）

for (int i = m; i < n; i++) {
	int min = location[0];
    int temp = 0;
    for (int j = 0; j < m; j++) {
    	if (location[j] < min) {
        	min = location[j];
            temp = j;
        }
    }
    location[temp] = min + arr[i]; //看吧，思路其实是很简单的*^__^*
}

那么剩下就非常简单了，附上代码就拜拜咯(∠ • ω <)~☆

#include <stdio.h>
int main() {
  
  //输入部分，没啥好看的
    int n, m;
    scanf("%d %d", &n, &m);
    int arr[10010], location[110];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    } 
  
  //当前接水人数n不足m
    if (n<=m) {
        m = n;
        for (int i = 0; i < m; i++) {
            location[i] = arr[i];
        }
    }
  
  //当前接水人数n比m多
    else {
        for (int i = 0; i < m; i++) {
            location[i] = arr[i];
        }
        for (int i = m; i < n; i++) {
            int min = location[0];
            int temp = 0;
            for (int j = 0; j < m; j++) {
                if (location[j] < min) {
                    min = location[j];
                    temp = j;
                }
            }
            location[temp] = min + arr[i];
        }
    }

  //判断哪个耗时最多就行
    int max = location[0];
    for (int i = 0; i < m; i++) {
        if (location[i] > max) {
            max = location[i];
        }
    }
    printf("%d", max);

    return 0;
}