自动搬运

查看原文

来自洛谷，原作者为

	落落的去 **

搬运于2025-08-24 23:13:17，当前版本为作者最后更新于2025-04-14 18:22:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意分析

给你一份 $n$ 的全排列 $a$，请你再给出一份 $n$ 全排列 $b$ 使得所有满足 $b_i>a_i$ 的 $i$ 的总和 $sumb$ 减去 所有满足 $b_i<a_i$ 的 $i$ 的总和 $suma$ 的差值最大。

如果 $a_i==b_i$ ，则都不得分。

思路分析

这不就是田忌赛马，考虑用下等马换掉对方的上等马。

比如样例中的 1 3 2 这个排列，我们可以摆出 2 1 3 就是用最下等的马换掉对方最上等的马，而且由于是全排列，所以剩下的所有位置一定可以排出都比对方大的排列。

但是，如果我们遇到了 2 1 3 这个排列，如果还摆出 3 2 1 得到的结果是 0 ，但是摆出 1 2 3 得到的结果是 1 ,所以我们还需要考虑对方的上等马得到的分数特别多，这个时候就需要也用我们的上等马和他抵消掉了。

我选择打表找找规律。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 2e5 + 10;

int a[100], n;
int t[100][100], cnt;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) a[i] = i;
	do
	{
		cnt++;
		for (int i = 1; i <= n; i++) {
			t[cnt][i] = a[i];
		}
	}while(next_permutation(a+1, a+1+n));
	
	for (int i = 1; i <= cnt; i++) {
		for (int z = 1; z <= n; z++) cout<<z<<" "; cout << endl;
		cout << "----------------" << endl;
		for (int z = 1; z <= n; z++) cout<<t[i][z]<<" "; cout<<endl;
		int maxn=INT_MIN, id_;
		for (int j = 1; j <= cnt; j++) {
			int sa = 0, sb = 0;
			for (int k = 1; k <= n; k++) {
				if (t[j][k] > t[i][k]) sa += k;
				else if(t[j][k] < t[i][k]) sb += k;
			}
			if(sa - sb > maxn)
			{
				maxn = sa - sb;
				id_ = j;
			}
		}
		for (int z = 1; z <= n; z++) cout<<t[id_][z]<<" "; cout<<endl<<endl;
	}
	return 0;
}

打完表恍然大悟，我们能确定的是对方最多只能拿到一天的分数，如果要给对方拿到这一天的分数，那么对方之前投入的比这天更多数字的天数我们一定会用相同的数字抵消掉。

那么我们可以用结构体存储天数和数字，然后按数字降序排列。

然后从最大的数字开始选择是否用 1 去田忌赛马，如果用 1 去田忌赛马，有可能不会是最优解，尤其是最大的数字在最后一天的时候。

所以还可以考虑直接用最大的数字去抵消对方的最大的数字，那么再考虑剩下的数字中最大的数字即可。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10;

struct node{
	int val, pos;
}a[N];

bool cmp(node x, node y)
{
	return x.val > y.val;
}
ll n;
ll sum; // 目前能获得的资源总数
ll ans;

int main()
{
	cin >> n;
	sum = (1 + n) * n / 2; // 总得分
	for (int i = 1; i <= n; i++) {
		cin >> a[i].val;
		a[i].pos = i;
	}
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		sum -= a[i].pos; // 选择到这里田忌赛马能否得到最大值
		ans = max(ans, sum - a[i].pos);
	}
	cout << ans;
	return 0;
}