[CSP-S模拟测试]:笨小猴（随机化）

题目传送门（内部题118）

输入格式

　　输入第一行是一个整数$n$，意义如以上所示。
　　接下来有$2n+1$行，每行为两个正整数，第$i$行的两个正整数分别代表$A_i$和$B_i$。

输出格式

　　如果无法选出$n+1$张卡片满足驴蛋蛋的要求，输出一个数$-1$。
　　否则输出$n+1$行，每行有一个正整数，表示选出的卡片编号（从$1$开始）。如果有多解，输出任意一组解均可

样例

样例输入：

2
4 2
9 4
5 3
7 5
8 1

样例输出：

3
4
2

数据范围与提示

样例$1$解释：

　　选择顺序随意，选择第二，三，四张三张卡片，$A$的总和为$21$，$B$的总和为$12$，均大于剩下的卡片$A,B$之和。

数据范围：

　　共$10$组测试数据
　　对于前$3$组测试数据有第$p$组中$N=2\times p+1$
　　对于后$7$组测试数据有第$p$组中$N=p\times 10,000$
　　对所有测试数据$1\leqslant A_i,B_i\leqslant 10^9$
　　如果你通过某种方法$hack$掉了评测插件，你可以申请获得该测试点的分数=ω=

题解

随机划，没了……

随机打乱序列，取前$n+1$个，判断是够可行，不可行接着打乱，肯定不会存在$-1$。

千万记得开$long\ long$！！！

时间复杂度：$\Theta($玄学$)$。

期望得分：$30$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int x,a,b;}e[300000];

int n;

long long suma,sumb;

int main()

{

	srand(time(NULL));scanf("%d",&n);

	for(int i=1;i<=2*n+1;i++)

	{

		e[i].x=i;

		scanf("%d%d",&e[i].a,&e[i].b);

		suma+=e[i].a;sumb+=e[i].b;

	}

	while(1)

	{

		long long A=0,B=0;

		random_shuffle(e+1,e+2*n+2);

		for(int i=1;i<=n+1;i++)

		{

			A+=e[i].a;

			B+=e[i].b;

		}

		if(2*A-suma>0&&2*B-sumb>0)

		{

			for(int i=1;i<=n+1;i++)printf("%d\n",e[i].x);

			return 0;

		}

	}

	return 0;

}

rp++

巴特西