Line Empire (Codeforces 1659C)
Tags: Greedy, binary search

You are an ambitious king who wants to be the Emperor of The Reals. But to do that, you must first become Emperor of The Integers.Consider a number axis. The capital of your empire is initially at $$$0$$$. There are $$$n$$$ unconquered kingdoms at positions $$$0<x_1<x_2<\ldots<x_n$$$. You want to conquer all other kingdoms.There are two actions available to you:   You can change the location of your capital (let its current position be $$$c_1$$$) to any other conquered kingdom (let its position be $$$c_2$$$) at a cost of $$$a\cdot |c_1-c_2|$$$.  From the current capital (let its current position be $$$c_1$$$) you can conquer an unconquered kingdom (let its position be $$$c_2$$$) at a cost of $$$b\cdot |c_1-c_2|$$$. You cannot conquer a kingdom if there is an unconquered kingdom between the target and your capital. Note that you cannot place the capital at a point without a kingdom. In other words, at any point, your capital can only be at $$$0$$$ or one of $$$x_1,x_2,\ldots,x_n$$$. Also note that conquering a kingdom does not change the position of your capital.Find the minimum total cost to conquer all kingdoms. Your capital can be anywhere at the end.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$)  — the number of test cases. The description of each test case follows.The first line of each test case contains $$$3$$$ integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq a,b \leq 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^8$$$).The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer  — the minimum cost to conquer all kingdoms.

Note: Here is an optimal sequence of moves for the second test case:  Conquer the kingdom at position $$$1$$$ with cost $$$3\cdot(1-0)=3$$$.  Move the capital to the kingdom at position $$$1$$$ with cost $$$6\cdot(1-0)=6$$$.  Conquer the kingdom at position $$$5$$$ with cost $$$3\cdot(5-1)=12$$$.  Move the capital to the kingdom at position $$$5$$$ with cost $$$6\cdot(5-1)=24$$$.  Conquer the kingdom at position $$$6$$$ with cost $$$3\cdot(6-5)=3$$$.  Conquer the kingdom at position $$$21$$$ with cost $$$3\cdot(21-5)=48$$$.  Conquer the kingdom at position $$$30$$$ with cost $$$3\cdot(30-5)=75$$$. The total cost is $$$3+6+12+24+3+48+75=171$$$. You cannot get a lower cost than this.

Sample Inputs:
4
5 2 7
3 5 12 13 21
5 6 3
1 5 6 21 30
2 9 3
10 15
11 27182 31415
16 18 33 98 874 989 4848 20458 34365 38117 72030

Sample Outputs:
173
171
75
3298918744

Solution (Python):
import math
from sys import stdin
from collections import Counter
output = ''

def run(n, a, b, nums):
    global output
    nums.insert(0, 0)
    n += 1
    max_cost = a * nums[n - 2] + b * nums[n - 1]
    position = n - 2
    back_moves = 0
    while position > 0:
        back_moves += 1
        backwards_distance = nums[position] - nums[position - 1]
        cost_diff = a * backwards_distance - b * backwards_distance * back_moves
        if cost_diff > 0:
            max_cost -= cost_diff
            position -= 1
        else:
            break
    output += str(max_cost) + '\n'
n = int(stdin.readline())
for x in range(0, n):
    test_info = stdin.readline().split(' ')
    n = int(test_info[0])
    a = int(test_info[1])
    b = int(test_info[2])
    nums = [int(x) for x in stdin.readline().split(' ')]
    run(n, a, b, nums)
print(output)

Solution (Python):
for i in range(int(input())):
    (n, a, b) = map(int, input().split())
    vh = list(map(int, input().split()))
    sm = sum(vh)
    rs = sm * b
    s = 0
    for j in range(n):
        s += vh[j]
        rs = min(rs, (a + b) * vh[j] + (sm - s - (n - j - 1) * vh[j]) * b)
    print(rs)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

def solve():
    (n, a, b) = map(int, input().split())
    arr = list(map(int, input().split()))
    q = deque([])
    ans = idx = curr = 0
    while idx < n:
        if not q or a > (n - idx) * b:
            q.append(idx)
            ans += (arr[q[-1]] - curr) * b
            idx += 1
            continue
        ans += (arr[q[0]] - curr) * a
        curr = arr[q.popleft()]
    print(ans)
for _ in range(int(input())):
    solve()