Edit

【pythonでABC181を解説】E - Transformable Teacher

問題概要

問題ページ

E - Transformable Teacher
E - Transformable Teacher

問題ページへ移動する

問題文

\(N\) 人の児童がおり、 \(i\) 番目の児童の身長は \(H_i\) です。
\(N\) は奇数です。

今から、先生であるあなたを含めた \(N+1\) 人で \(2\) 人 \(1\) 組を \(\large\frac{N+1}2\) ペア組みます。

あなたの目標は、それぞれのペアの身長の差の合計を最小化することです。
すなわち、 \(i\) 番目のペアの身長の組を \((x_i, y_i)\) としたとき、 \(\displaystyle \sum_{i=1}^{(N+1)/2}|x_i-y_i|\) を最小化したいです。

あなたには \(M\) 個の変身形態があり、 \(i\) 番目の変身形態での身長は \(W_i\) です。

あなたの変身形態とペアの組み方を工夫することで、それぞれのペアの身長の差の合計が最小でいくつにできるか求めてください。

制約

  • 入力はすべて整数
  • \(1 \leq N, M \leq 2 \times 10^5\)
  • \(N\) は奇数
  • \(1 \leq H_i \leq 10^9\)
  • \(1 \leq W_i \leq 10^9\)

問題の考察

ACコード

import sys
import bisect
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    h = list(map(int, input().rstrip('\n').split()))
    w = list(map(int, input().rstrip('\n').split()))
    if n == 1:
        mn = 10 ** 20
        for v in w:
            mn = min(mn, abs(v - h[0]))
        print(mn)
    else:
        h.sort()
        w.sort()
        even, odd = [0] * n, [0] * n
        for i in range(1, n, 2):
            even[i] = h[i] - h[i-1]
        for i in range(2, n, 2):
            odd[i] = h[i] - h[i-1]
        even = list(itertools.accumulate([0] + even))
        odd = list(itertools.accumulate(odd + [0]))
        mn = 10 ** 20
        for v in w:
            pos = bisect.bisect_right(h, v)
            mn = min(mn, odd[-1] - odd[pos] + even[pos] - even[0] + abs(v - (h[pos]if pos % 2 == 0 else h[pos - 1])))
        print(mn)


if __name__ == '__main__':
    solve()

-Edit
-