MVP_DukeX's blog

By MVP_DukeX, history, 5 weeks ago, In English

There is an array with size $$$N$$$. Given an integer $$$K$$$, each time you can choose two element in this array, let's call them $$$x$$$ and $$$y$$$, remove them and add $$$K-x-y$$$ into the array. After $$$n-1$$$ operations, there is only one element in the array. What's the maximum possible value of this element?

There are Q queries, each queries contains an integer K. Answer the queries indepently.

$$$N, Q <= 300000 $$$

$$$K, a[i] <= 10^9$$$

Sample:

$$$N=4$$$

$$$a=[1\ 2\ 3\ 4]$$$

$$$K=[3\ 4\ 5\ 6\ 7]$$$

$$$Ans=[7\ 6\ 5\ 4\ 5]$$$

Expain for the sample: for $$$K=3$$$, we can choose $$$[1,2]$$$ and add $$$(3-1-2)$$$ to the array, so that the array is now $$$[0,3,4]$$$

then we can choose $$$[3,4]$$$ and add $$$(3-3-4)$$$ to the array, now the array is $$$[0,-4]$$$

At last, we can left $$$3-0-(-4)=7$$$ which is the maximum possible value.

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

is there any absolute values involved in the problem statement as i don't think for a=[1,2,3,4] with k=3 will end up to be 7 for k-x-y after n-1 iterations in any possible way if considering absolute is not the case

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -6 Vote: I do not like it

    I guess it should have been K-x+y just for the first query

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    first choose x=1, y=2, and got a=[0,3,4]

    then choose x=3, y=4, and got a=[0,-4]

    so the last element will be 3-(-4)-0=7

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

      if we brute force then calculate the sum of total elements and ans= ((2-n)/2)*k + sum; n is even then use ans as it is else subtract the minimum possible element twice from ans

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

        let k=1000 and n = 6, a = [1 2 3 4 5 6]

        we can get ans = 1001

        choose [1,2] then a = [997 3 4 5 6]

        choose [997,5] then a = [-2 3 4 6]

        choose [-2,3] then a = [999 4 6]

        choose [999,6] then a = [-5 4]

        finally a = [1001]