HDU-6785 Permutation 题解

题目大意

给你一串数字序列1~n，问你最多交换m对数字，最多能构成多少对逆序对。

解题思路

刚开始花了十分钟， a了两道，写到了这个题。

觉得这个题目不难。

写完之后，wa了一万遍。。

卡了好久，就没打了。

后面一看，发现自己思路出了点问题。

其实就是一个很简单的题目。

首先为了逆序对最多，肯定是优先交换队列首尾。

然后队列不断向中间移动。

当时不知道怎么想的，脑袋一抽，想成了第一位移动，最后一位不动了。。

那么首先考虑能够构造出n~1的次数，很显然是$\large \frac {n}{2}$次。

答案就是从1加到n-1。

如果$\large m<\frac {n}{2}$，则说明不能全部到过来。

这个时候就需要自己找出公式了。

可以把交换m次之后的序列分为三份。

最前面那一份，分别与后面所有的数构成逆序对。

答案为n-1加到n-m。

中间那一份，每个都与最后面那一份构成逆序对。

易知中间的区间为$[m+1,n-m]$。

最后面的数的个数为m个。

所以答案为$(n-2m)*m$。

最后面的那一份，每个数也都与后面的数构成逆序对。

（之前就是忘了这个，wa了好久。

答案为1加到m-1。

我的代码思路用的是前缀和，其实用数学的等差求和也可以，应该会更快。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e6 + 5;
ll sum[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	for (ll i = 1; i <= 1e6; i++) {
		sum[i] = sum[i - 1] + i;
	}
	while (t--) {
		ll n, m;
		cin >> n >> m;
		if (n == 1 || !m) {
			cout << 0 << endl;
			continue;
		}
		ll ans;
		int t = n / 2;
		if (t <= m)	ans = sum[n - 1];
		else {
			ans = sum[n - 1] - sum[n - m - 1] + (n - 2 * m) * m + sum[m - 1];
		}
		cout << ans << endl;
	}
	return 0;
}