unomti

用户名：uq_99084910152

访问量：7148

签　名：

等　　级
排　　名	951
经　　验	3293
参赛次数	9
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

题意理解方面的题解
浏览：187

通俗易懂的全排列 c++解法
浏览：887

你可能喜欢

通俗易懂的全排列 c++解法

　　作者: unomti　　　　发表时间：2021-05-04 21:17:06 浏览：887　|　评论：1　

原题链接：排队买票

### 思路:
我开始做的时候有些不理解，网上的大部分题解是关于卡特兰数的（不用说，我看不懂hah）

然后我就在想这个问题，起初我想用回溯法插入元素，不过最后放弃了，太复杂了。

然后我就想这个排队是什么时候是合法的，很好想出来，就是每个2前面至少对应着一个1。话虽如此但我们如何检验？我起初想暴力解决但实现起来思路比较复杂，而且时间复杂度高。

**然后我突然想到了多数元素的摩尔投票法，然后我就想到了用一个num记录，num如果有1就++，有2就--，如果过程中num<0则证明存在有一个2没有一个1对应。**

但是到此为止还没有结束，我想的是判断类似1122的所有全排列包括重复的。（这种应该可以回溯写出来，但是感觉还是比较复杂的），然后我就改成初始前面的1为0~K-1，后面的2为K~N-1 所以小于K的就相当于是1了，大于K的就相当于是2了。对于这种0123的序列我们可以直接使用next_permutation();

### 参考ac题解
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int N, K, M;

int main() {
	while (cin >> N >> K >> M) {
		int a[N], res = 0;
		for (int i=0; i<K; i++) {
			a[i] = i;
		}
		for (int i=K; i<N; i++) {
			a[i] = i;
		}
		do {
			int flag = 0;
			// check每个全排列， num务必要初始化 
			int num = 0;
			for (int i=0; i<N; i++) {
				if (a[i] >= K) {
					num--;
				} else {
					num++;
				}
				if (num < 0) {
					flag = 1;
					break;
				}
			}
			if (flag == 0) {
//				for (int i=0; i<N; i++) {
//					cout << a[i];
//				}
//				cout << "\n";
				res++;
			}
			
		} while (next_permutation(a,a+N));
	
	
		cout << res << "\n";
	}
	return 0;
}
```

**思路可能不成熟，如有错误，还望指正**

0.0分

13 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

梨花

谢谢大佬！

2021-12-05 14:52:49

unomti

TA的其他文章

你可能喜欢

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-求车速（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C二级辅导-进制转换（C语言代码）

通俗易懂的全排列 c++解法

评论区

精彩推荐

钟神赛车（C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

分糖果（C++代码）

哥德巴赫曾猜测（C语言代码）

【简单计算】（C语言代码）

WU-整除问题（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

完数（C语言代码）

C语言训练-数字母（C语言代码）

unomti

TA的其他文章

你可能喜欢

C语言考试练习题_一元二次方程 （C语言代码）

C语言训练-求车速 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C二级辅导-进制转换 （C语言代码）

通俗易懂的全排列 c++解法

评论区

精彩推荐

钟神赛车 （C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

分糖果 （C++代码）

哥德巴赫曾猜测 （C语言代码）

【简单计算】 （C语言代码）

WU-整除问题 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

完数 （C语言代码）

C语言训练-数字母 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-求车速（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

钟神赛车（C++代码）

分糖果（C++代码）

哥德巴赫曾猜测（C语言代码）

【简单计算】（C语言代码）

WU-整除问题（C++代码）

完数（C语言代码）

C语言训练-数字母（C语言代码）