二分,WA on 7求调
查看原帖
二分,WA on 7求调
965685
yyrwlj楼主2024/5/6 14:37
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2005;
typedef long long LL;
int a[N], b[N];
struct Node{
	int x, y;
	LL v;
}c[2000005];
bool cmp(Node A,Node B)
{
	return A.v < B.v;
}
inline LL Abs(LL x)
{
	if (x < 0)
		return -x;
	return x;
}
int main()
{
	int n, m;
	scanf("%d", &n);
	LL suma = 0, sumb = 0;
	for (int i=1;i<=n;i++)
		scanf("%d", &a[i]), suma += a[i];
	scanf("%d", &m);
	for (int i=1;i<=m;i++)
		scanf("%d", &b[i]), sumb += b[i];
	LL ans = Abs(suma - sumb);
	vector<pair<int, int> > path;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (Abs(suma - 2 * a[i] + 2 * b[j] - sumb) < ans)
			{
				ans = Abs(suma - 2 * a[i] + 2 * b[j] - sumb);
				path.clear();
				path.push_back({i, j});
			}
	int tot = 0;
	for (int i=1;i<m;i++)
		for (int j=i+1;j<=m;j++)
			c[++tot] = {i, j, b[i] + b[j]};
	sort(c + 1, c + tot + 1, cmp);
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			const LL x = (suma + sumb) / 2 - suma + a[i] + a[j];
			int l = 1, r = tot, pos = tot;
			while (l <= r)
			{
				int mid = (l + r) >> 1;
				if (c[mid].v <= x)
					pos = mid, l = mid + 1;
				else
					r = mid - 1;
			}
			if (Abs(suma - 2 * a[i] - 2 * a[j] + 2 * c[pos].v - sumb) < ans)
			{
				ans = Abs(suma - 2 * a[i] - 2 * a[j] + 2 * c[pos].v - sumb);
				path.clear();
				path.push_back({i, c[pos].x});
				path.push_back({j, c[pos].y});
			}
			if (++pos > tot)
				continue;
			if (Abs(suma - 2 * a[i] - 2 * a[j] + 2 * c[pos].v - sumb) < ans)
			{
				ans = Abs(suma - 2 * a[i] - 2 * a[j] + 2 * c[pos].v - sumb);
				path.clear();
				path.push_back({i, c[pos].x});
				path.push_back({j, c[pos].y});
			}
		}
	printf("%lld\n%d\n", ans, path.size());
	for (auto i : path)
		printf("%d %d\n", i.first, i.second);
	return 0;
}
2024/5/6 14:37
加载中...