JZOJ5405 & AtCoder Grand Contest 001 F. Permutation

题目大意

给出一个长度为\(n\)的排列\(P\)与一个正整数\(k\).

你需要进行如下操作任意次, 使得排列\(P\)的字典序尽量小.

对于两个满足\(|i-j|>=k\) 且\(|P_i-P_j| = 1\) 的下标\(i\)与\(j\)，交换\(P_i\) 与\(P_j\).

解题思路

若构造\(Q_{p_i}=i\), 即\(Q_i\)表示\(i\)在\(P\)序列中的位置, 则容易发现, 当\(Q\)的字典序最小的时候, \(P\)的字典序就达到了最小.

于是可以把原问题转换成求最小的\(Q\)的字典序. 根据题目中的条件, 稍加思考把原来的交换操作定义到序列\(Q\)上: 对于两个满足\(|i-j|=1\)且\(|Q_i-Q_j|>=k\)的下标\(i\)与\(j\), 交换\(Q_i\)与\(Q_j\).

那么我们考虑, 对于怎样的\(i\)和\(j\), 它们经过任意次操作之后的字典序的相对位置都不变.

对于每一个\(L\), 它最右能够交换到的位置就是最大的\(R\)满足对于\(\forall j \in [i,R]\)都有\(|Q_L-Q_j|>=k\). 于是\(R+1\),也就是最小的\(R'\)满足\(|Q_L-Q_{R'}|<k\),它们\((L\text{与}R')\)的相对顺序是不会变的. 显然这个东西可以通过线段树做到\(O(n\log{n})\).

于是对于每一个\(L\), 找到对应的\(R'\), 连一条边\((R',L)\), 表示\(R'\)一定在\(L\)之后. 对这个图拓扑排序, 就得到了字典序相对顺序的倒序. 倒着做一遍, 在过程中使用大根堆维护即可就出最小的字典序. 最后还原即可.

时间复杂度\(O(n\log{n})\).

后记

有一说一, 自己对这种题还是缺乏基本的经验. 对于拓扑排序确定大小顺序的题也缺乏一定的转化能力和理解能力. 这种题之后遇到了如果没做出来也要整理.

#include <queue>

#include <cstdio>

#include <cstring>

#define N 500010

#define INF 0x3f3f3f3f

#define init(a, b) memset(a, b, sizeof(a))

#define fo(i, a, b) for(int i = (a); i <= (b); ++i)

#define fd(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

inline int read()

{

	int x = 0; char ch = getchar();

	while(ch < '0' || ch > '9')	ch = getchar();

	while(ch >= '0' && ch <= '9')	x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

	return x;

}

inline int min(int a, int b){return a < b ? a : b;}

int n, k, p[N], q[N];

priority_queue<int> h;

int in[N], last[N], pre[N << 1], to[N << 1];

inline void add(int u, int v){static int tot = 0; ++tot, ++in[v], to[tot] = v, pre[tot] = last[u], last[u] = tot;}

namespace SGT

{

	#define ls t << 1

	#define rs ls | 1

	#define mid ((l + r) >> 1)

	int tr[N << 4];

	inline void pushup(int t){tr[t] = min(tr[ls], tr[rs]);}

	void build(int t, int l, int r)

	{

		if(l == r)	return (void)(tr[t] = INF, 0);

		build(ls, l, mid); build(rs, mid + 1, r);

		pushup(t);

	}

	void update(int t, int l, int r, int w, int v)

	{

		if(l == r)	return (void)(tr[t] = v, 0);

		w <= mid ? update(ls, l, mid, w, v) : update(rs, mid + 1, r, w, v);

		pushup(t);

	}

	inline void update(int w, int v){update(1, 1, n, w, v);}

	int query(int t, int l, int r, int fl, int fr)

	{

		if(fl <= l && r <= fr)	return tr[t];

		int ret = INF;

		fl <= mid && (ret = min(ret, query(ls, l, mid, fl, fr)));

		fr > mid && (ret = min(ret, query(rs, mid + 1, r, fl, fr)));

		return ret;

	}

	inline int query(int fl, int fr){return query(1, 1, n, fl, fr);}

	#undef ls

	#undef rs

	#undef mid

}

int main()

{

	freopen("permutation.in", "r", stdin);

	freopen("permutation.out", "w", stdout);

	scanf("%d %d", &n, &k);

	fo(i, 1, n)	scanf("%d", &p[i]), q[p[i]] = i;

	SGT::build(1, 1, n);

	fd(i, n, 1)

	{

		int pos = SGT::query(q[i], min(q[i] + k - 1, n));

		pos < INF && (add(q[pos], q[i]), 0);

		pos = SGT::query(max(1, q[i] - k + 1), q[i]);

		pos < INF && (add(q[pos], q[i]), 0);

		SGT::update(q[i], i);

	}

	fo(i, 1, n)

		if(!in[i])

			h.push(i);

	fd(w, n, 1)

	{

		int u = h.top(); h.pop(); p[w] = u;

		for(int i = last[u]; i; i = pre[i])

			if(!(--in[to[i]]))	h.push(to[i]);

	}

	fo(i, 1, n)	q[p[i]] = i;

	fo(i, 1, n)	printf("%d\n", q[i]);

	return 0;

}

巴特西

JZOJ5405 & AtCoder Grand Contest 001 F. Permutation

题目大意

解题思路

后记

最新文章

热门文章