自动搬运

查看原文

来自洛谷，原作者为

	Jason0211 AFO

搬运于2025-08-24 21:27:48，当前版本为作者最后更新于2023-08-15 19:44:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到标签里有随机化，乱写了一下直接过了。

这里提供一种随机化乱搞的做法：

首先，将数列从小到大将原序列排序，由于我们只需要使两组数的和尽可能大，根据贪心，我们可以将最小的 $k$ 个分为一组，才能保证其他两组尽可能大（这里想一想就能明白了，无需证明）。

然后，对后面 $2k$ 个数进行随机化排列，然后直接判断是否符合要求，不符合则继续，符合则直接输出。这里，我们可以选择使用 $\operatorname{shuffle}$ 函数对原序列进行随机化打乱，实测出解率很高，每个测试点均可跑到 $4$ 毫秒以内。

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int sum,id;
}a[185];
bool cmp(Node a,Node b)
{
	return a.sum<b.sum;
}
inline int read()
{
	int x = 0, f = 1;
	char ch = 0;
	while (!isdigit(ch)) {ch = getchar(); if (ch == '-') f =-1;}
	while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
	return x * f;
}

int main()
{
	int k;
	k=read();
	int len=3*k;
	for(int i=1;i<=len;i++)
	{
		a[i].sum=read();
		a[i].id=i;
	}
	sort(a+1,a+len+1,cmp);
	for(int i=1;i<=k;i++)
	{
		printf("%d\n",a[i].id);
	}
	while(true)
	{
		random_shuffle(a+k+2,a+len+1);
		int ans=0,cnt=0,re=500*k;
		for(int i=k+1;i<=2*k;i++)
		{
			ans+=a[i].sum;
			if(ans>re)
			{
				cnt++;
				break;
			}
		}
		ans=0;
		for(int i=2*k+1;i<=len;i++)
		{
			ans+=a[i].sum;
			if(ans>re)
			{
				cnt++;
				break;
			}
		}
		if(cnt==2)
		{
			for(int i=k+1;i<=len;i++)
			{
				printf("%d\n",a[i].id);
			}
			break;
		}
	}
	return 0;
}