CF513B1 Permutations 题解

Content

给定两个整数 \(n,m\)。定义 \(f(p)=\sum\limits_{l=1}^n\sum\limits_{r=l}^n\min\limits_{i=l}^rp_i\)，其中 \(p\) 为一个长度为 \(n\) 的排列。现在，请你求出所有使得 \(f(p)\) 最大的长度为 \(n\) 的排列中，字典序第 \(m\) 小的排列。

数据范围：\(1\leqslant n\leqslant 8\)。

Solution

看到数据范围马上想到一种很 naive 的 \(O(n!\cdot n^3)\) 的做法：先枚举所有的排列求出最大的 \(f(p)\)，然后再枚举所有的排列扫到使得 \(f(p)\) 最大的字典序第 \(m\) 小的排列。

next_permutation 可以更方便地枚举全排列，具体看代码。

Code

namespace Solution {

	const int N = 17;

	int n, m, mx, p[N];

	iv Main() {

		read(n, m); F(int, i, 1, n) p[i] = i;

		do {

			int sum = 0;

			F(int, l, 1, n) F(int, r, l, n) {

				int mn = 10;

				F(int, i, l, r) mn = min(mn, p[i]);

				sum += mn;

			}

			mx = max(mx, sum);

		}while(next_permutation(p + 1, p + n + 1));

		int cnt = 0;

		F(int, i, 1, n) p[i] = i;

		do {

			int sum = 0;

			F(int, l, 1, n) F(int, r, l, n) {

				int mn = 10;

				F(int, i, l, r) mn = min(mn, p[i]);

				sum += mn;

			}

			if(sum == mx) {

				cnt++;

				if(cnt == m) {

					F(int, i, 1, n) printf("%d%c", p[i], " \n"[i == n]);

					break;

				}

			}

		}while(next_permutation(p + 1, p + n + 1));

		return;

	}

}

巴特西

CF513B1 Permutations 题解

Content

Solution

Code

最新文章

热门文章