【日常小测】苹果和雪梨

题目大意

给你$n(n \le 3000)$个梨，$n$个苹果。每个梨有个权值$a_i$，每个苹果有个权值$b_i$
现在让你求出一种匹配关系，使得梨与苹果一一配对，使得获益最大。
设$i$号梨对应$f_i$号苹果，定义收益为$\sum\limits_{i=1}^{n}{a_i \cdot b_{f_i}}-\max\{a_i \cdot b_{f_i}\}$

解题报告

这题有一个非常显然的$O(n^4)$的暴力：

$O(n^2)$枚举最大值是哪一对
对于其他梨，贪心选择最大的、可以选的苹果配对

这种暴力优化一下，据说可以优化到$O(n^3)$

但我们仔细想一想，这种XJB枚举最大值很不优雅，会做很多重复的动作
于是我们考虑从小到大枚举最大值是哪一对
考虑我们此时将涉及到的四个点更改匹配关系即可
时间复杂度：$O(n^2 \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3009;
const int M = N * N;

LL n,tot,vout,ans,mx,a[N],b[N],p[N],q[N]; 
struct Match{int x,y;LL val;}m[M];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) a[i] = read();
	for (int j=1;j<=n;j++) b[j] = read();
	sort(a+1, a+1+n); sort(b+1, b+1+n);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			m[++tot].val = a[i] * b[j];	
			m[tot].x = i; m[tot].y = j;
		}
	}
	static auto cmp = [](const Match &A, const Match &B) {return A.val < B.val || (A.val == B.val && A.x < B.x) || (A.val == B.val && A.x == B.x && A.y < B.y);};
	sort(m+1, m+1+tot, cmp);
	for (int i=1;i<=n;i++) 
		mx = max(mx, a[i] * b[n-i+1]);
	for (int i=n;i;i--) {
		for (int j=n;j;j--) {
			if (!q[j] && a[i] * b[j] <= mx) {
				q[j] = i; p[i] = j;
				ans += a[i] * b[j];
				break;
			}
		}
	}
	vout = ans - mx;
	for (int i=1,x,y,nx,ny;i<=tot;i++) {
		if (m[i].val <= mx) continue;
		x = m[i].x; y = m[i].y; nx = p[x]; ny = q[y];
		p[ny] = nx; q[nx] = ny; p[x] = y; q[y] = x;
		ans += a[x] * b[y] + a[ny] * b[nx];
		ans -= a[x] * b[nx] + a[ny] * b[y];
		vout = max(vout, ans - m[i].val);
	}
	printf("%lld\n",vout);
	return 0;
}