自动搬运

查看原文

来自洛谷，原作者为

	AuCloud 这只小羊很懒，什么都没留下来

搬运于2025-08-24 22:30:34，当前版本为作者最后更新于2021-04-12 20:52:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

来自一个考场上被自己一顿阴间操作把D1T1正解文件搞没了的sb

提供思路，不一定正确，欢迎各大佬hack（但是过了民间数据

对所有的值按大小排序，不论 $a$ 面 $b$ 面

记录每个值对应是 $a$ 面或者 $b$ 面

于是现在我们得到了一个长度为 $2N$ 的序列。

显然我们的答案就是这个序列的某个子序列两端的差值

具体求可以用双指针——我们可以删除前面一段和后面一段，要求是

• 删除的 $a$ 面总数不能超过要求

• 不能同时删除同一张卡的两面

对于第一条就拿个变量动态记录一下删了多少个就好

第二条开个桶维护就好

总时间复杂度$O(N\log N)$，瓶颈在排序

代码如下

#include <bits/stdc++.h>
using namespace std;
struct hehe{
	long long a, num;
	int op;
	bool operator < (hehe b) const
	{
		return a < b.a;
	}
}a[2000001];
bool used[2000001];
int main()
{
	// freopen("card3.in", "r", stdin);
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i].a);
		a[i].num = i;
		a[i].op = 1;
	}
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[n + i].a);
		a[i + n].num = i;
		a[i].op = 1;
	}
	sort(a + 1, a + n * 2 + 1);
	int l = 0, r = n * 2 + 1, now = 0;
	while(!used[a[l + 1].num] && now + a[l + 1].op <= k) now += a[l + 1].op, used[a[l + 1].num] = 1, l++;
	while(!used[a[r - 1].num] && now + a[r - 1].op <= k) now += a[r - 1].op, used[a[r - 1].num] = 1, r--;
	long long ans = 1000000000000;
	while(l >= 0)
	{
		ans = min(a[r - 1].a - a[l + 1].a, ans);
		used[a[l].num] = 0;
		now -= a[l].op;
		l--;
		while(!used[a[r - 1].num] && now + a[r - 1].op <= k) now += a[r - 1].op, used[a[r - 1].num] = 1, r--;

	}
	cout << ans << endl;
}

碎碎念：亲手把自己送出省队，我现在心态良好