Glory Addicts (Codeforces 1738A)
Tags: Greedy, sortings

The hero is addicted to glory, and is fighting against a monster. The hero has $$$n$$$ skills. The $$$i$$$-th skill is of type $$$a_i$$$ (either fire or frost) and has initial damage $$$b_i$$$. The hero can perform all of the $$$n$$$ skills in any order (with each skill performed exactly once). When performing each skill, the hero can play a magic as follows:   If the current skill immediately follows another skill of a different type, then its damage is doubled.  In other words,   If a skill of type fire and with initial damage $$$c$$$ is performed immediately after a skill of type fire, then it will deal $$$c$$$ damage;  If a skill of type fire and with initial damage $$$c$$$ is performed immediately after a skill of type frost, then it will deal $$$2c$$$ damage;  If a skill of type frost and with initial damage $$$c$$$ is performed immediately after a skill of type fire, then it will deal $$$2c$$$ damage;  If a skill of type frost and with initial damage $$$c$$$ is performed immediately after a skill of type frost , then it will deal $$$c$$$ damage. Your task is to find the maximum damage the hero can deal. 

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The following lines contain the description of each test case.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), indicating the number of skills. The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), where $$$a_i$$$ indicates the type of the $$$i$$$-th skill. Specifically, the $$$i$$$-th skill is of type fire if $$$a_i = 0$$$, and of type frost if $$$a_i = 1$$$. The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$), where $$$b_i$$$ indicates the initial damage of the $$$i$$$-th skill. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output the maximum damage the hero can deal.

Note: In the first test case, we can order the skills by $$$[3, 1, 4, 2]$$$, and the total damage is $$$100 + 2 \times 1 + 2 \times 1000 + 10 = 2112$$$.In the second test case, we can order the skills by $$$[1, 4, 2, 5, 3, 6]$$$, and the total damage is $$$3 + 2 \times 6 + 2 \times 4 + 2 \times 7 + 2 \times 5 + 2 \times 8 = 63$$$.In the third test case, we can order the skills by $$$[1, 2, 3]$$$, and the total damage is $$$1000000000 + 1000000000 + 1000000000 = 3000000000$$$.In the fourth test case, there is only one skill with initial damage $$$1$$$, so the total damage is $$$1$$$. 

Sample Inputs:
4
4
0 1 1 1
1 10 100 1000
6
0 0 0 1 1 1
3 4 5 6 7 8
3
1 1 1
1000000000 1000000000 1000000000
1
1
1

Sample Outputs:
2112
63
3000000000
1

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if 1 not in a:
        print(sum(b))
    elif 0 not in a:
        print(sum(b))
    else:
        p = []
        q = []
        for i in range(n):
            if a[i] == 1:
                q.append(b[i])
            else:
                p.append(b[i])
        p = sorted(p, reverse=True)
        q = sorted(q, reverse=True)
        summ = 0
        if len(p) > len(q):
            summ += p[-1] + sum(q) * 2 + sum(p[:len(q)]) * 2 + sum(p[len(q):-1])
        elif len(p) < len(q):
            summ += q[-1] + sum(p) * 2 + sum(q[:len(p)]) * 2 + sum(q[len(p):-1])
        else:
            b.sort()
            summ += b[0] + sum(b[1:]) * 2
        print(summ)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

def main():
    for _ in range(int(input())):
        x = int(input())
        skills = list(map(int, input().split()))
        damges = list(map(int, input().split()))
        fire = skills.count(0)
        frost = skills.count(1)
        if fire == 0 or frost == 0:
            print(sum(damges))
        elif fire == frost:
            damges = sorted(damges)
            print(sum(damges[1:]) * 2 + damges[0])
        else:
            frosts = [damges[f] for f in range(len(skills)) if skills[f] == 1]
            fires = [damges[f] for f in range(len(skills)) if skills[f] == 0]
            frosts = sorted(frosts)
            fires = sorted(fires)
            if frost > fire:
                diff = frost - fire
                frosts = sum(frosts[0:diff]) + sum(frosts[diff:]) * 2
                fire = sum(fires) * 2
                print(frosts + fire)
            else:
                diff = fire - frost
                fire = sum(fires[0:diff]) + sum(fires[diff:] * 2)
                frosts = sum(frosts * 2)
                print(frosts + fire)
    pass
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()
''

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().strip().split()))
    ls = list(map(int, input().strip().split()))
    a = l.count(0)
    b = n - a
    co = 0
    if a == n or b == n:
        co = sum(ls)
    elif a == b:
        co = sum(ls) * 2 - min(ls)
    elif a < b:
        (l0, l1) = ([], [])
        for i in range(n):
            if l[i] == 0:
                l0.append(ls[i])
            else:
                l1.append(ls[i])
        l0.sort(reverse=True)
        l1.sort(reverse=True)
        co += sum(ls)
        for i in range(a):
            co += l1[i] + l0[i]
    else:
        (l0, l1) = ([], [])
        for i in range(n):
            if l[i] == 0:
                l0.append(ls[i])
            else:
                l1.append(ls[i])
        l0.sort(reverse=True)
        l1.sort(reverse=True)
        co += sum(ls)
        for i in range(b):
            co += l1[i] + l0[i]
    print(co)