给我一个offer球球啦：又在骗我投简历

CHN_ByteDance：真是一条合理而造福大家的建言。

LambdaZJU：再贴一种方法哈，昨天吃饭时候跟朋友讨论，换了一种思路，昨天晚上做了一下。 #include <iostream> #include <vector> #include <string> #include <queue> #include <unordered_map> #include <map> #include <algorithm> using namespace std; //输入参数 int n;//输入n个数 int k;//有序对k对 vector<int> a;//输入序列a，包含1~n的n个数，有若干个数（不超过10个）是0 //输出参数 int cnt=0;//合法排列的数目 //输出perm数组，用于测试 void printperm(const vector<vector<int> > &perm) { for(int i=0;i<perm.size();i++) { for(int j=0;j<perm[0].size();j++) cout<<perm[i][j]<<" "; cout<<endl; } } //第一步，选出用于全排列的数 void chooseperm(vector<int> &permuse) { vector<int> permtemp; int permnum=0;//需要全排列的数的个数 int temp=0; for(int i=1;i<=n;i++)//初始化为1~n permtemp.push_back(i); for(int i=0;i<a.size();i++)//移除输入中已有的数 { if(a[i]) { remove(permtemp.begin(),permtemp.end(),a[i]); temp++; } } permnum=n-temp;//n-移除的数，即需要全排列的数的个数 for(int i=0;i<permnum;i++)//得到用于全排列的vector permuse.push_back(permtemp[i]); } //第二步，对第一步选出的数全排列 void creatperm(vector<vector<int> > &perm,vector<int> &permuse) { do{ perm.push_back(permuse); }while(next_permutation(permuse.begin(), permuse.end())); } //第三步，拼接第二步得到的全排列的二维vector和已有的输入 void insertperm(vector<vector<int> > &perminsert,const vector<vector<int> > &perm) { for(int i=0;i<perm.size();i++) { vector<int> tempinsert; int q=0; for(int p=0;p<n;p++) { if(a[p]) tempinsert.push_back(a[p]); else tempinsert.push_back(perm[i][q++]); } perminsert.push_back(tempinsert); } } //第四步，逐行验证其有序对是否为k，统计符合的个数 void count( const vector<vector<int> > &choose) { for(int i=0;i<choose.size();i++) { int ktemp=0; vector<int> temp=choose[i]; for(int j=0;j<temp.size();j++) { for(int jj=j+1;jj<temp.size();jj++) { if(temp[j]<temp[jj]) ktemp++; } } if(ktemp==k) cnt++; } } int main(){ //输入 cin>>n>>k; for(int i=0;i<n;i++) { int temp; cin>>temp; a.push_back(temp); } //第一步，选出用于全排列的数 vector<int> permuse;//用于全排列的数 chooseperm(permuse); cout<<"用于全排列的数"<<endl; for(int i=0;i<permuse.size();i++) cout<<permuse[i]<<" "; cout<<endl; //第二步，对第一步选出的数全排列 vector<vector<int> > perm;//得到全排列的二维vector creatperm(perm,permuse); cout<<"全排列"<<endl; printperm(perm); //第三步，拼接第二步得到的全排列的二维vector和已有的输入 vector<vector<int> > perminsert; insertperm(perminsert,perm); cout<<"符合模板的排列"<<endl; printperm(perminsert); //第四步，逐行验证其有序对是否为k，统计符合的个数 count(perminsert); cout<<"符合的排列个数"<<endl; cout<<cnt<<endl; }