2020百度之星初赛三Permutation/C++解法

Problem Description

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

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

Input

第一行一个正整数 test (1≤test≤100000) 表示数据组数。

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

Output

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

Sample Input

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

Sample Output

0
0
1
3
5
6

分析

首位交换能使得逆序对数目更大，然后第2项与n-2项交换，以此类推。当m大于n/2时直接取n/2。第一次交换，逆序对数目增加(n-1)+(n-2)对，第二次交换，逆序对数目增加(n-3)+(n-4)对，故每次公差为4，项数为m，列出求和公式。

首项为2n-3
末项为(2n-3)-4(m-1)
求和公式化简为m(2n-2m-1)

C++代码

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    long long t,n,m,ans;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        m=min(n/2,m);
        ans=m*(2*n-2*m-1);
        ans<=0?cout<<0<<endl:cout<<ans<<endl;
    }
    return 0;
}