HBC209387TwoMatchings题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

A permutation of length n is an array p=[p_1, p_2, ldots, p_n] p=[p 1 ​ ,p 2 ​ ,…,p n ​ ], which contains every integer from 1 to n (inclusive) and each number appears exactly once. For example, p=[3,1,4,6,2,5] is a permutation of length 6. Let's call a permutation is a matching if and only if p_i ne i p i ​  ​ =i and p_{p_i} = i p p i ​ ​ =i for all valid i. You are given an array a=[a_1, a_2, ldots, a_n] a=[a 1 ​ ,a 2 ​ ,…,a n ​ ] ( 0 le a_i le 10^9 0≤a i ​ ≤10 9 , n ge 4 n≥4 and n is even). Define the cost of a permutation is (sumlimits_{i=1}^n abs(a_i-a_{p_i})) / 2 ( i=1 ∑ n ​ abs(a i ​ −a p i ​ ​ ))/2. Define two matchings p, q are combinable if and only if p_i ne q_i p i ​  ​ =q i ​ for all i from 1 to n. Please find two combinable matchings such that the sum of the cost of these two matchings is as small as possible. Output the sum.

想要在职场中立于不败之地？那就来试试全网最全C++题库，让您在练习中快速提升技能。

标签： HBC209387TwoMatchings题解