UVa 13044 - Robot Hands

Source

A Bangladeshi Contest at SUST(20151212)
UVa 13044

問題概要

要素数 $N$ の整数列 $\{A_i\}_{i=1}^N, \{B_i\}_{i=1}^N$ が与えられる.
$2$ つの配列の各要素を以下の手順で $N$ 回マッチングしていく.
マッチングされた要素は次の回からマッチングの候補にならない.

  1. $|A_i-B_j|$ が最小となるような $(A_i,B_j)$ をマッチングする
  2. 候補が複数存在するなら,$A_i+B_j$ が最大となるようなものを選ぶ
  3. まだ候補が複数存在するなら,$i$ が最小となるようなものを選ぶ
  4. まだ候補が複数存在するなら,$j$ が最小となるようなものを選ぶ

マッチングされた順に,どの要素とどの要素がマッチングされたかを求める問題.

解法

候補をpriority_queueなどに突っ込んでおいてシミュレーションする.
各 $B_i$ について,$B_i$ より大きいもののうちで最も小さい $A_i$ と,$B_i$ より小さいもののうちで最も大きい $A_i$ などを二分探索などで探してそれらのみを考慮してpriority_queueに突っ込む.
候補の片割れが既に使われていて成立しなくなった場合は,新しい候補をpriority_queueに突っ込み直すなどとしていく.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月18日11時47分13秒
Last modified: 2015年12月16日02時08分14秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: