题解 | #[NOIP2010]接水问题#
[NOIP2010]接水问题
https://ac.nowcoder.com/acm/problem/16600
考察重点：数组，排序
首先根据题意，有n名学生要用m个水龙头来接水，要求我们找出所有学生都接完水需要花的时间。
很明显，重点不在于所有人一起花了多久，我们需要“反过来想”（逆向思考）：找出所有同学花的时间，其实就是找出哪个水龙头用水花的总时间最长（比如1号水龙头总共用了wi = 114来装水，2号用了wj = 514来装水，那最终花的总时间只取决于耗时最多的那个(木桶效应)，所以总共花了514秒，）也就是说，重点不在于下一个是谁来装水，而是下一个轮到哪一个水龙头来放水给学生用。关键在于找出那个耗时最多的水龙头，它的总用时即为所有学生需要花的时间。
由于结果跟n, m的对应大小有关，我们需要分别讨论：
- 当前接水人数n不足m（即n<=m）
- 这种情况下，m个水龙头是够用的，那就一个萝卜一个坑，有多少个学生要接就给多少水龙头，一一对应找出耗时最多的就好了
for (int i = 0; i < m; i++) {
location[i] = arr[i]; //最简单の情况
}
- 当前接水人数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;
}