Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are very hard-working. But the elevator in that hall always drives them crazy. Why? Because there is only one elevator in GaoKe Hall, while there are hundreds of companies in it. Every morning, people must waste a lot of time waiting for the elevator.

Hal, a smart guy in ZSoft, wants to change this situation. He wants to find a way to make the elevator work more effectively. But it's not an easy job.

There are 31 floors in GaoKe Hall. It takes 4 seconds for the elevator to raise one floor. It means:

It costs (31 - 1)×4 = 120 seconds if the elevator goes from the 1-st floor to the 31-st floor without stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it will cost 30×4 + 29×10 = 410 seconds (It is not necessary to calculate the stopping time at 31st floor). In another way, it takes 20 seconds for the workers to go up or down one floor. It takes 30×20 = 600 seconds for them to walk from the 1-st floor to the 31-st floor. Obviously, it is not a good idea. So some people choose to use the elevator to get a floor which is the nearest to their office.

After thinking over for a long time, Hal finally found a way to improve this situation. He told the elevator man his idea: First, the elevator man asks the people which floors they want to go. He will then design a stopping plan which minimize the time the last person need to arrive the floor where his office locates. For example, if the elevator is required to stop at the 4-th, 5-th and 10-th floor, the stopping plan would be: the elevator stops at 4-th and 10-th floor. Because the elevator will arrive 4^th floor at 3×4 = 12 second, then it will stop 10 seconds, then it will arrive 10^th floor at 3×4 + 10 + 6×4 = 46 second. People who want to go 4-th floor will reach their office at 12 second, people who want to go to 5-th floor will reach at 12 + 20 = 32 second and people who want to go to 10-th floor will reach at 46 second. Therefore it takes 46 seconds for the last person to reach his office. It is a good deal for all people.

Now, you are supposed to write a program to help the elevator man to design the stopping plan, which minimize the time the last person needs to arrive at his floor.

Input 

The input consists of several testcases. Each testcase is in a single line as the following:

It means, there are totally n floors at which the elevator need to stop, and n = 0 means no testcases any more. f₁ f₂ ... f_n are the floors at which the elevator is to be stopped (n30, 2f₁ < f₂ < ... < f_n31). Every number is separated by a single space.

Output 

For each testcase, output the time the last reading person needs in the first line and the stopping floors in the second line. Please note that there is a summary of the floors at the head of the second line. There may be several solutions, any appropriate one is accepted. No extra spaces are allowed.

Sample Input 

3 4 5 10
1 2
0

Sample Output 

46
2 4 10
4
1 2

---

題目描述：

電梯現在在 1 樓，而要載一些人從 1 樓到指定樓層，每個人可以選擇搭電梯搭到一半改走樓梯，

或者直接走樓梯，問最後一個人抵達指定樓層的最少時間。(即最小化最大時間。)

電梯每上升一層消耗 4 秒，停留於一層開門時消耗 10 秒。

人藉由樓梯往下或往下爬一層消耗 20 秒。

題目解法：

二分答案，當然也可以選擇 DP，dp[i][j] 表示電梯當前停留在 i 時，把 j 個人送到指定樓層的最少時間。

當指定一個時間後，檢查在限定的時間內能不能將所有人送到指定樓層的策略。

貪婪策略：電梯盡可能在越高的地方停留，即加上要往下爬的那個人不超過指定時間。

因此可以得到當電梯停留在 j 層時，而有一個人目標 i 樓層，此時電梯已經停留 num 次。

則必須符合 (j'-1)*4 + num*10 + (j'-i)*20 <= limit_time ==> 得到 j' 下次停留地方。

而同時相對應的，這個時候放人並不是只能往下爬，往上爬也是等價的。

因此可以忽略中間一段人的需求，得到下次考慮的人的目標樓層。

(j'-1)*4 + num*10 + (i'-j')*10 <= limit_time ==> i' (含)以下的不用考慮。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int f[105];
vector<int> stopFloor;
int check(int limit, int mx) {
	int lfloor = limit/20+2;// floor of last person be stopped.
	int sfloor = 1;// now stopping floor.
	int scnt = 0;// stopped times.
	vector<int> buf;
	while(lfloor <= mx) {
		while(lfloor <= mx && f[lfloor] == 0)
			lfloor++;
		if(scnt*10+(lfloor-1)*4 > limit)
			return 0;
		int nfloor = (limit-10*scnt+20*lfloor+4)/24;//next stopping floor.
		lfloor = (limit-10*scnt+16*nfloor+4)/20+1;
		sfloor = nfloor;
		//if(nfloor <= mx)
		buf.push_back(nfloor);
		scnt++;
	}
	stopFloor = buf;
	return 1;
}
int main() {   
	//freopen("in.txt","r+t",stdin);
    //freopen("out.txt","w+t",stdout);
	int n;
	int i, j, k, x;
	while(scanf("%d", &n) == 1 && n) {
		memset(f, 0, sizeof(f));
		int mx = 0;
		for(i = 0; i < n; i++) {
			scanf("%d", &x), f[x] = 1;
			mx = max(mx, x); 
		}
		int l = 0, r = mx*(14), mid;
		int ret = 0;
		while(l <= r) {
			mid = (l+r)/2;
			if(check(mid, mx))
				ret = mid, r = mid-1;
			else
				l = mid+1;
		}
		printf("%d\n", ret);
		printf("%d", stopFloor.size());
		for(i = 0; i < stopFloor.size(); i++)
			printf(" %d", stopFloor[i]);
		puts("");
	}
	return 0;
}