6785. Permutation

HDOJ 6785. Permutation

2020 年百度之星·程序设计大赛 - 初赛三

• 6783. Discount
• 6784. Game
• 6785. Permutation
• 6786. Intersection

题目：6785. Permutation

问题描述：

一开始有 n 个数，他们按 1…n 的顺序排列，要求交换最多 m 对数字（同一个数字可以参与多次交换），使得逆序对数目最大。

对于一个序列 A，如果存在正整数 i,j 使得 1≤i<j≤n 而且 A[i]>A[j]，则 <A[i],A[j]> 这个有序对称为 A 的一个逆序对。

输入：

第一行一个正整数 test (1≤test≤100000) 表示数据组数。
对于每组数据，一行两个整数 n，m (1≤n≤1000000,0≤m≤1000000) 表示数字个数和最多可以交换的数字对数。

输出：

对于每组数据，一行一个整数表示答案。

样本输入：

6
1 1
2 0
2 1
3 1
4 1
4 2

样本输出：

0
0
1
3
5
6

方法：数学

思路：根据题目寻找规律，可以发现按照第一个元素跟最后一个交换、第二个元素跟倒数第二个交换这样的规律交换即可使得逆序对数目最大，巧妙利用等差数列求和公式可尽快得出结果。当交换次数m >= n/2时，可实现将原来的序列全部逆序（如原序列1、2、3、4、5、6，当m >= n/2时，可使得原序列变为6、5、4、3、2、1），此个序列拥有最大逆序对，可用(n - 1) * n/ 2得出逆序对数目。

当交换次数m < n/2时,此时不能将原序列全部逆序（如原序列1、2、3、4、5、6，当m == 2时交换后为6、5、3、4、1、2，当m == 1时交换后为6、2、3、4、5、1，当m == 0时交换后为1、2、3、4、5、6），这时可用((n - 1) + (n - m)) * m / 2计算与前部分组合时的逆序对数（以上前面例子来说明，当m == 2时，交换后序列为6、5、3、4、2、1，前部分指的就是6、5），可用(n - 2 * m) * m计算与中间部分组合时的逆序对数（以上前面例子来说明，当m == 2时，交换后序列为6、5、3、4、2、1，中间部分指的就是3、4），可用((m - 1) + 0) * m / 2计算与后部分组合时的逆序对数（以上前面例子来说明，当m == 2时，交换后序列为6、5、3、4、2、1，后部分指的就是2、1），计算全部的逆序对数只需将前、中、后的逆序相加即可，整理可得(2 * n - m - 1) * m / 2 + (n - 2 * m) * m + (m - 1) * m / 2。

运行数据：执行用时：1294MS，内存消耗：13792K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int test = sc.nextInt();

        while (test-- > 0) {
            long n = sc.nextLong();
            long m = sc.nextLong();
            long result = 0;
            if (n / 2 <= m) {
                result = (n - 1) * n / 2;
            } else {
                result = (2 * n - m - 1) * m / 2 + (n - 2 * m) * m + (m - 1) * m / 2;
            }
            System.out.println(result);
        }
    }
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！