preetham's blog

By preetham, history, 5 years ago, In English

There are $$$ n $$$ people who are living in their own houses $$$ h_1, h_2, h_3 \dots , h_n $$$ located on the X-axis. A boy who can move with a speed of $$$ 1 unit/sec $$$, needs to visit all the houses. We need to find the minimum waiting time of the people (sum of waiting time of all the people)?

The initial position of the boy is $$$ x $$$

$$$ Constraints : 1 <= n <= 1000, -10^6 <= h_i , x <= 10^6 $$$

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

From live contest?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are two possible ways to go to every person optimally. Either go to complete right and then left or the opposite. Check whichever is min

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should minimize sum not maximum. Try on this scenario:

        $$$x=0$$$
        $$$h=[-1000, -1, 1, 1000]$$$
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Consider $$$ x = 10 $$$ and houses at $$$ 1, 9, 11, 19 $$$
        the correct answer is $$$ 44 $$$