#PQJ1727x8913. QOJ 1727_8913

    ID: 2697 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2024 集训贪心排序

QOJ 1727_8913

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

  1. 交换第 和第 个居民,幸福值变成了 。
  2. 交换第 和第 个居民,幸福值变成了 。
  3. 交换第 和第 个居民,幸福值变成了 。 居民们现在按照要求的幸福值非递减的顺序排列了。没有比 次更少的交换次数可以得到非递减的排 列。 样例2输入 1 4 2 1 -1 1 -1 样例2输出 1 -1 样例2解释 没有一系列的交换可以使居民按照幸福值非递减的顺序排列。 数据范围和提示 对于所有的数据,有 , 。 的范围 子任务编号 分值 额外限制 对于所有的 , 对于所有的 , 对于所有的 , 对于所有的 , 对于所有的 , 对于所有的 , 没有额外的限制 没有额外的限制