层板等分衣柜 简单实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 板子是否可以移动
bool canMove(const vector<int> &t, vector<int> zs, const vector<int> &target) {
	for (int i = 0; i < t.size(); i++) {
		int tmp = t[i];
		if (zs[tmp] > target[tmp]) {
			if (tmp - 1 >= 0 && zs[tmp - 1] >= target[tmp])
				return false;
			else
				zs[tmp] = target[tmp];
		} else if (zs[tmp] < target[tmp]) {
			if (tmp + 1 < zs.size() && zs[tmp + 1] <= target[tmp])
				return false;
			else
				zs[tmp] = target[tmp];
		}
	}
	return true;
}

// 木板移动顺序的全排列
void recursion(vector<vector<int>> &res, vector<int> &idx, int index) {
	if (index == idx.size() - 1 )
		res.push_back(idx);
	else {
		for (int i = index; i < idx.size(); i++) {
			swap(idx[i], idx[index]);
			recursion(res, idx, index + 1);
			swap(idx[i], idx[index]);
		}
	}
}

// 排序方法
bool cmp(vector<int> a, vector<int> b) {
	int tmpa = 0, tmpb = 0;
	for (int i = 0; i < a.size(); i++) {
		tmpa = tmpa * 10 + a[i] % 10;
	}
	for (int i = 0; i < b.size(); i++) {
		tmpb = tmpb * 10 + b[i] % 10;
	}
	return tmpa < tmpb;
}

void solve(vector<vector<int>> &res, vector<int> &zs, int n) {
	// 木板目标位置
	vector<int> target;
	int k = 2000 / (n + 1);
	target.push_back(k);
	for (int i = 1; i < n; i++)
		target.push_back(target[i - 1] + k);

	vector<vector<int>> allres;
	vector<int> idx;
	for (int i = 0; i < n; i++)
		idx.push_back(i);

	recursion(allres, idx, 0);


	for (int i = 0; i < allres.size(); i++)
		if (canMove(allres[i], zs, target)) {
			res.push_back(allres[i]);
		}
}

int main() {
	// 输入
	int n;
	vector<int> zs;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		zs.push_back(tmp);
	}

	vector<vector<int>> res;

	solve(res, zs, n);
	// 结果排序
	sort(res.begin(), res.end(), cmp);

	// 输出
	for (int i = 0; i < res.size(); i++) {
		for (int j = 0; j < res[0].size(); j++) {
			cout << res[i][j] + 1 << " ";
		}
		cout << endl;
	}
	return 0;
}