首页 > Inverse Pair
开通博客写题解
头像 QQQQQQ5292
发表于 2021-07-27 16:43:40
题目描述：给你一个数组a，a[i]可以加1或者不加，求进行所有操作完后最小的逆序对数思路：先把所有的逆序对数求出来，然后再找满足(a[i]>a[j]&&i<j&&a[i]==a[j]+1)条件的对数，再用所有的逆序对数减去满足条件对数就可以的出最小对数。A 展开全文
去ta的博客 赞 (2) 回复(3) 收起
头像 sunny_forever
发表于 2021-07-28 20:25:13
I 题题解 思路 题意:通过对 a 中若干个元素 加1(每个元素只能加1次)，使得逆序对的数目变少，问逆序对数目 最少可变为几因为 a 是 1 到 n 的全排列，即 [1,n] 中每个元素均出现且只出现一次所以 我们每次 加1操作 最多消掉一个逆序对 ，该逆序对 满足 i < j && 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”