Codeforces Round #298 (Div. 2) - D. Handshakes

贪心 + 构造

题意

有 \(n(1<=n<=2*10^5)\) 个人，每分钟有一个人进入房间，房间里任意 3 个人可以组队开始工作并一直持续下去，且只要房间里至少有 3 个人，他们就可以在任意时间开始组队工作；每当一个人进来时，会给当前房间里没有在工作的人握手

给出数组 \(a_i\), 表示第 i 个人跟 \(a_i\) 个人握手了，求这 n 个人进入房间的顺序

思路

1. 下标从 0 开始便于取模

2. 第 i 个人只可能跟 \(i\equiv j\mod3且j<=i\) 个人握手

3. 因为任意时刻都可以有 3 个人组队，所以贪心地尽量满足握手次数的多的人，再让当前房间里空闲的人组队

4. 可以用 multiset 维护，把余数相同的 \(a_i\) 放到同一个 multiset 中

   在第 i 个人进入时，设房间里有 now 个人，如果 st 中存在 now，就让这个人与 now 个人握手；若不存在，则要有人组队才行，找到 st 中比 now 小的最大的数，让其余人都组队

​ 然而 multiset tle on test63。。。可能常数太大了

​ 可以用 set<pair<int, int> > 来代替，存的是 {a[i], i}

​ 这样输出答案时也更方便

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
#define endl "\n"

typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10;
int n;
int a[N];
int cnt[3];
int ans[N];
set<PII> st[3];
void solve()
{
	for (int i = 0; i < n; i++)
	{
		st[a[i] % 3].insert(make_pair(a[i], i));
		cnt[a[i] % 3]++;
	}
	if (cnt[0] != (n + 2) / 3 || cnt[1] != (n + 1) / 3 || cnt[2] != n / 3)
	{
		puts("Impossible");
		return;
	}
	int now = 0;
	for (int i = 0; i < n; i++)
	{
		int id = i % 3;
		auto it = st[id].lower_bound(make_pair(now, -1));
		PII c;
		if (it != st[id].end() && it->first == now)
		{
			c = *it;
			ans[i] = c.second + 1;
		}
		else
		{
			if (it == st[id].begin())
			{
				puts("Impossible");
				return;
			}
			it--;
			c = *it;
			ans[i] = c.second + 1;
		}
		st[id].erase(it);
		now = c.first + 1;
	}
	puts("Possible");
	for (int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	puts("");
}
int main()
{
	// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	solve();
    return 0;
}