P1088 [noip2004 popularity group question 4] Martians ← next_ permutation

【 Title source 】
https://www.luogu.com.cn/problem/P1088

【 Title Description 】
Man finally landed on the land of Mars and met the mysterious Martians . Neither humans nor Martians can understand each other's language , But our scientists have invented a way to communicate digitally . This method of communication is like this , First , Martians tell human scientists a very large number , Scientists decipher the meaning of this number , Then add a small number to the large number , Tell the Martians the results , As a human answer .
Martians represent numbers in a very simple way ―― Break your fingers . Martians have only one hand , But this hand has thousands of fingers , These fingers line up , They are numbered 1,2,3,⋯. Any two fingers of a Martian can exchange positions at will , That's how they count .
A Martian demonstrated how to count with his fingers with a human hand . If you put five fingers ―― thumb 、 index finger 、 Middle finger 、 The ring finger and little finger are numbered 1,2,3,4 and 5, When they are arranged in the normal order , To form the 5 digit 12345, When you exchange the positions of the ring finger and little finger , Will form the 5 digit 12354, When you completely reverse the order of the five fingers , Will form the 54321, In all that can be formed 120 individual 5 In figures ,12345 Minimum , It said 1;12354 The second smallest , It said 2;54321 Maximum , It said 120. The following table shows that only 3 A finger can form 6 individual 3 The number of digits and the numbers they represent ：
123 → 1
132 → 2
213 → 3
231 → 4
312 → 5
321 → 6
Now you are lucky to be the first person on earth to communicate with Martians . A Martian will show you his fingers , Scientists will tell you a small number to add . Your task is , Add the numbers that Martians use their fingers to the numbers that scientists tell you , And change the order of Martian fingers according to the addition result . Input data to ensure that the result will not exceed the range that Martian fingers can represent .

【 Input format 】
There are three lines .
First line a positive integer N, Indicates the number of Martian fingers （1≤N≤10000）.
The second line is a positive integer M, Represents the small integer to be added （1≤M≤100）.
The next line is 1 To N this N An arrangement of integers , Space off , Indicates the order of Martian fingers .  

【 Output format 】
N It's an integer , Indicates the changed order of Martian fingers . Every two adjacent numbers are separated by a space , There must be no extra space .

【 explain / Tips 】 
about 30% The data of ,N≤15.  
about 60% The data of ,N≤50.  
about 100% The data of ,N≤10000.

【 Algorithm analysis 】
utilize STL Of next_permutation, It can be easily solved Full Permutation . In essence, this problem can be transformed into the problem of finding complete permutation .
Essentially , The question is to “ The sequence of Martians ” Translate into “ Number of people on earth ” after , Plus a small “ Number of people on earth ”m. after , Then translate their sum into “ The sequence of Martians ”. In code implementation , Will function next_permutation perform m The output of times is the desired result .

next_permutation See ：
https://cplusplus.com/reference/algorithm/next_permutation/

Example 1 of complete permutation problem ：

#include <bits/stdc++.h>
using namespace std;

const int maxn=100;
int a[maxn];
int n;

int main() {
	cin>>n;
	for(int i=0; i<n; i++) cin>>a[i];
	sort(a,a+n);
	do {
		for(int i=0; i<n; i++)
			cout<<a[i]<<" ";
		cout<<endl;
	} while(next_permutation(a,a+n));
	
	return 0;
}

/*
in:
3
1 3 2

out:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/

Complete permutation problem Example 2 ：

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	string s;
	getline(cin,s);
	
	sort(s.begin(),s.end());  //very important
	
	int cnt=0;
	do{
		cout<<s<<endl;
		cnt++;
	} while(next_permutation(s.begin(),s.end()));
	
	cout<<"Having "<<cnt<<" kinds of permutations"<<endl;
	
	return 0;
}


 
/*
in:
121

out:
112
121
211
*/

【 Algorithm code 】

#include <bits/stdc++.h>
using namespace std;

const int maxn=10010;
int a[maxn];

int main() {
	int n,m;
	cin>>n>>m;

	for(int i=0; i<n; i++)
		cin>>a[i];
		
	for(int i=0; i<m; i++)
		next_permutation(a,a+n);
	
	for(int i=0; i<n-1; i++) {
		cout<<a[i]<<" ";
	}
	cout<<a[n-1];
	
	return 0;
}



/*
in:
5
3
1 2 3 4 5

out:
1 2 4 5 3
*/

【 reference 】
https://blog.csdn.net/hnjzsyjyj/article/details/118616680
https://blog.csdn.net/Study_Study_X/article/details/122916226
https://www.luogu.com.cn/problem/P1088