uvalive 2949 - Elevator Stopping Plan(贪心+二分）
题目连接：2949 - Elevator Stopping Plan
题目大意：某个抠门的公司只有一个电梯， 现在有n 个人从1楼， 他们有各自想要到达的楼层， 然后电梯每上一楼需要4 秒， 每在一个楼层开门需要10 秒， 然后然爬楼梯的话需要20一楼。问， 如何用最短的时间让所有人都到达各自想要到的楼层。
解题思路：因为人可以爬楼梯， 所以可以在某个楼层下楼之后走楼梯到达想要到的楼层， 只要在最后一个人到达之前就可以。 对于时间可以采取二分的方式搜索， 所以只要判断某个时间能否将所有人送到指定楼层就可以了。 对于判断我们可以用贪心去做， 尽量让电梯停在较高的楼层，只要剩余的时间够使得人走到自己的楼层就可以了。
#include <stdio.h>#include <string.h>const int N = 32;int n, mid, top, cnt, vis[N], stop[N];void read() { int t; top = 0; memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) {scanf("%d", &t);vis[t] = 1;if (t > top)top = t; }}bool judge(int tmp) { cnt = 0; memset(stop, 0, sizeof(stop)); for (int i = tmp / 20 + 2; i <= top; i++) {while (!vis[i] && i < top) i++;int t = (i - 1) * 4 + cnt * 10;if (tmp < t)return false;t = (tmp - 10 * cnt + 20 * i + 4) / 24;i = (tmp - 10 * cnt + 16 * t + 4) / 20;stop[cnt++] = t; } return true;}int solve() { int L = 0, R = 14 * (top - 1); while (L < R) {mid = (L + R + 1) / 2;if (mid == R)break;if (judge(mid)) R = mid;else L = mid; } return mid;}int main() { while (scanf("%d", &n) == 1 && n) {read();judge(solve());printf("%d\n%d", mid, cnt);for (int i = 0; i < cnt; i++) printf(" %d", stop[i]);printf("\n"); } return 0;}