Hello, bosses, I am free to fly.

Careful people may have noticed that I didn’t cover the seventh question.

This is because question seven is so hard. It’s not that the code is hard to implement, it’s that getting the idea across is hard.

The positive solution to this problem is the Garsia-Wachs algorithm, which constructs an optimal binary search tree with known key values and query probabilities.

I have been thinking about it for about three weeks, but I have not come up with a more understandable explanation, and I do not want to copy the book, so I give up temporarily, and come back to make up for it when I have an Epiphany.

The Art of Computer Programming, Vol. 3, Section 6.2.2, Algorithm G and Lemma W, Lemma X, Lemma Y, Lemma Z. [PDF download link]. (mp.weixin.qq.com/s/wTkvRxgcG…).

POJ 1744 Elevator Stopping Plan.

Topic link

Poj.org/problem?id=…

Topic describes

There are H floors in GaoKe Hall.

It takes 4 seconds for the elevator to raise one floor. It means: It costs (N −1)∗4(n-1)*4(n−1)∗4 seconds if the elevator goes from the 1 st floor to the NTH floor without stopping. And the elevator stops 10 second once.

So, if the elevator stops at each floor, it will cost
$(n-1)*4+(n-2)*10$ seconds (It is not necessary to calculate the stopping time at nth floor).

In another way, it takes 20 seconds for the workers to go up or down one floor. It takes
$(n-1)*20$ seconds for them to walk from the 1 st floor to the nth floor.

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 4th , 5th and 10th floor, the stopping plan would be: The elevator stops at 4th and 10th floor. Because the elevator will arrive 4th floor at 3∗4=123*4=123∗4=12 second, then it will stop 10 seconds, Then it will arrive 10 th floor at 3∗4+10+6∗4=463*4+10+6*4=463∗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.

The title input

The input consists of several test cases. Each test case is in a single line as the following: n f1 f2 … fnn\ f_1\ f_2\ … \ f_nn f1 f2 … fn

It means, there are totally n floors at which the elevator need to stop, and n = 0 means no testcases any more.

f1 f2 … fn are the floors at which the elevator is to be stopped (1<=n<=30000, 2<= f1< f2 … fn<=30000).

Every number is separated by a single space.

The title output

For each testcase, output the time the last reading person needs in the a single line

Enter the sample

3, 4, 5, 10, 1, 2, 0

The output sample

46
4

Generally see the largest minimum value, the earliest and the most late time point and other similar words, can be considered with dichotomy to solve.

For a given input, there must be an optimal solution, assuming that the optimal solution consumes TTT seconds. Then for any time constraint t’ ≥tt’ \ge tt’ ≥t, there is a solution. For any t “

It is not difficult to find that this conforms to the premise of dichotomy — monotonicity. The question then becomes whether, on a given input, everyone can be sent to a given floor in midmidmid seconds. T ≤ MIDt \le midt≤mid; otherwise t>midt\gt midt>mid. Next, we solve this existential problem by transforming it into an interval coverage problem.

Let’s first assume that in the optimal scheme, the elevator has SSS stops, the floor of the third stop is FiF_iFi, and the time point for stopping at that floor is TiT_iTi. Since the elevator is initially on the first floor, let F0=1, T0=0F_0 =1, \ T_0 = 0F0=1, T0=0.

We make each stop cover all floors within [Li,Ri][L_i,R_i][Li,Ri]. Overlay means that the employees, at the TiT_iTi moment, walk down the elevator in FiF_iFi, and can walk to any of the layers in [Li,Ri][L_i,R_i][Li,Ri] within mid− − TIMids-t_imid −Ti seconds. It is not difficult to conclude:

• 
  $L_i = F_i – \lfloor (mid-T_i)/20 \rfloor$
• 
  $R_i = F_i + \lfloor (mid-T_i)/20 \rfloor$

Since all employees must arrive at their respective floors within midMIDMID time, the SSS stops will cover the input F1, F2… fnf_1,\ f_2,\ … \ f_nf1, f2, … Fn.

The problem then becomes to construct FiF_iFi, TiT_iTi, LiL_iLi, RiR_iRi. Then use greedy thinking to construct:

• Make each section as long as possible – this makes SSS as small as possible, i.e. the time spent docking is smaller.
• Any two intervals have no intersection — intersection means waste.

L0=1L_0 = 1L0=1, R0=⌊mid20⌋+1R_0 = \lfloor \frac{mid}{20} \rfloor+1R0=⌊20mid⌋+1. Then can be known (Fi – 1, Ti – 1, Li – 1, Ri – 1) (F_ 1} {I -, T_ {1} I -, L_ {1} I -, R_ {1} I -) (Fi – 1, Ti – 1, Li – 1, Ri – 1) under the premise of Solving (Fi, Ti, Li, Ri) (F_ {I}, T_ {I}, L_ {I}, R_ {I}) (Fi, Ti, Li, Ri).

Because to cover all f1, F2… fnf_1,\ f_2,\ … \ f_nf1, f2, … If the first fxf_xfx greater than Ri−1R_{i-1}Ri−1 is LiL_{I}Li, then

$L_i = f_x$

The following inequalities are listed based on Fi−1F_{i-1}Fi−1 and LiL_iLi:

$10+4(F_i – F_{i-1}) + 20(F_i – L_i) + T_{i-1} \le mid$

Transposition to:

$24F_i\le mid+4F_{i-1}+20L_i-10-T_{i-1}$

Take the maximum:

$F_i = \lfloor \frac{mid+4F_{i-1}+20L_i-10-T_{i-1}}{24} \rfloor$

Easy:

• 
  $T_i = T_{i-1} + 10 + 4(F_i-F_{i-1})$
• 
  $R_i = F_i + \lfloor \frac{mid-T_i}{20} \rfloor$

T ≤ MIDT \le MIDt ≤mid, otherwise t> MIDt \gt midt>mid.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <math.h>
#include <map>
#include <set>
#include <vector>

using namespace std;

int f[30000];

bool check(int mid, int n) {
  int f0 = 1, t0 = 0, l0 = 1, r0 = mid/20 + 1;
  int i = 0;
  int stop_cost = 0;
  while (i < n) {
    / / looking for fx
    while (f[i] <= r0) {
      i++;
    }
    if (i < n) {
      int l1 = f[i];
      int f1 = (mid+4*f0+20*l1-stop_cost-t0)/24;
      int t1 = t0 + stop_cost + (f1-f0)*4;
      int r1 = f1 + (mid-t1)/20;
      // There is not enough time left
      if (f1 == f0) {
        return false;
      }
      stop_cost = 10; l0 = l1, r0 = r1, t0 = t1, f0 = f1; }}return true;
}

int main(a) {
  int n;
  while(scanf("%d", &n) && n) {
    for (int i = 0; i < n; i++) {
      scanf("%d", &f[i]);
    }
    int L = (f[n- 1]- 1) *4, R = (f[n- 1]- 1) *10;

    while(L <= R) {
      int mid = (L+R)>>1;
      if (check(mid, n)) {
        R = mid- 1;
      } else {
        L = mid+1; }}printf("%d\n", R+1);
  }
  return 0;
}
Copy the code