#2148. Line Town
Line Town
Line Town
题目描述
2023 Canadian Computing Olympiad Day 1, Problem 3 Line Town Time Limit: 2 seconds Problem Description The N residents of Line Town have arranged themselves in a line. Initially, the residents have happiness values of h1, h2, . . . , hN from left to right along the line. Since you are the mayor of Line Town, you are implementing the third pillar of your plan entitled “Community, Candy, and Organization” (CCO). As such, you have taken the may- oral power to swap the resident’s locations. In one swap, you may tell two adjacent residents to swap their positions in the line. However, this swap will cause both residents to negate their happiness values. You would like to perform some swaps so that the residents’ happiness values are in non- decreasing order from left to right in the line. Determine whether this is possible, and if so, the minimum number of swaps needed. Input Specification The first line of input contains a single integer N. The next line of input contains N integers h1, . . . , hN (−109 ≤hi ≤109), the happiness values of the residents from left to right. Marks Awarded Bounds on N Bounds on hi 1 ≤N ≤2 000 |hi| = 1 for all i 3 marks 1 ≤N ≤500 000 |hi| = 1 for all i 3 marks 1 ≤N ≤2 000 |hi| ≤1 for all i 3 marks 1 ≤N ≤500 000 |hi| ≤1 for all i 4 marks 1 ≤N ≤2 000 |hi|̸ = |hj| for all i̸ = j 4 marks 1 ≤N ≤500 000 |hi|̸ = |hj| for all i̸ = j 3 marks 1 ≤N ≤2 000 2 marks No additional constraints. 1 ≤N ≤500 000 3 marks No additional constraints. Output Specification On a single line, output the minimum number of swaps, or −1 if the task is impossible. Sample Input 1 6 -2 7 -1 -8 2 8 Output for Sample Input 1 3 Explanation of Output for Sample Input 1 It is possible to perform 3 swaps as follows:
- Swap the 2nd and 3rd resident so that the line becomes [−2, 1, −7, −8, 2, 8].
- Swap the 4th and 5th resident so that the line becomes [−2, 1, −7, −2, 8, 8].
- Swap the 3rd and 4th resident so that the line becomes [−2, 1, 2, 7, 8, 8]. The residents are now arranged in non-decreasing order of happiness values as required. No non-decreasing arrangement can be obtained with less than 3 swaps. Sample Input 2 4 1 -1 1 -1 Output for Sample Input 2 -1 Explanation of Output for Sample Input 2 There is no sequence of swaps that will place residents in non-decreasing order of happiness values.
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
-2 7 -1 -8 2 8
3
样例 2
4
1 -1 1 -1
-1