#2221. 0418 t1
0418 t1
0418 t1
题目描述
时间限制:1s 空间限制:512MB 题面描述 线条小镇的 个居民排成了一条线。最初,居民们从左到右沿着线的幸福值为 。 你是线条小镇的镇长,你正在实施你的名为「社区、糖果和组织」(CCO)的计划。因此,你拥有了交 换居民位置的权力。在一次交换中,你可以让两个相邻的居民交换他们在线中的位置。但是,这次交换 会导致两个居民的幸福值取反。 你想要知道是否能进行一些交换,使得居民的幸福值从左到右按非递减的顺序排列。如果可能,需要的 最少交换次数是多少。 输入格式 第一行包含一个整数 。 第二行包含 个整数 ,表示从左到右的居民的幸福值。 输出格式 输出一行一个整数,表示最少的交换次数,如果任务不可能完成输出 。 样例1输入 1 6 2 -2 7 -1 -8 2 8 样例1输出 1 3 样例1解释 可以进行 次交换,如下所示:
- 交换第 和第 个居民,幸福值变成了 。
- 交换第 和第 个居民,幸福值变成了 。
- 交换第 和第 个居民,幸福值变成了 。 居民们现在按照要求的幸福值非递减的顺序排列了。没有比 次更少的交换次数可以得到非递减的排 列。 样例2输入 1 4 2 1 -1 1 -1 样例2输出 1 -1 样例2解释 没有一系列的交换可以使居民按照幸福值非递减的顺序排列。 数据范围和提示 对于所有的数据,有 , 。 的范围 子任务编号 分值 额外限制 对于所有的 , 对于所有的 , 对于所有的 , 对于所有的 , 对于所有的 , 对于所有的 , 没有额外的限制 没有额外的限制
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
-2 7 -1 -8 2 8
3
样例 2
4
1 -1 1 -1
-1