2017届网易内推笔试-机器学习（数据挖掘）编程第二题求解
昨晚这题没做出来，不甘心，不甘心，不甘心啊，难道只能枚举了吗？求大神攻破，以身相许了！！！！！！！
大致题意(如果有问题望指正，谢谢)：
课桌上n个格子摆放成一行，里面放着1~n的正整数（乱序），有几个（不超过10个）格子看不清是什么数字，
但是牛牛记得整个序列中有k个有序对，即当 i<j 时，A[i]<A[j]。求满足所有条件的序列有多少种？
输入：第一行输入n k，第二行输入序列，看不清的数字用0代替，其中1<n<100，1<k<10000000000
例：
输入：
5 5
4 0 0 2 0
输出：
2
ps:满足条件的2种序列可以找到为：4 3 1 2 5、4 1 5 2 3（均满足有5个有序对）
/********************************************************************************************************/
//谢谢牛友的提示，以下纯手写，望批评指正！！！
#网易##C++工程师#大致题意(如果有问题望指正，谢谢)：
课桌上n个格子摆放成一行，里面放着1~n的正整数（乱序），有几个（不超过10个）格子看不清是什么数字，
但是牛牛记得整个序列中有k个有序对，即当 i<j 时，A[i]<A[j]。求满足所有条件的序列有多少种？
输入：第一行输入n k，第二行输入序列，看不清的数字用0代替，其中1<n<100，1<k<10000000000
例：
输入：
5 5
4 0 0 2 0
输出：
2
ps:满足条件的2种序列可以找到为：4 3 1 2 5、4 1 5 2 3（均满足有5个有序对）
/********************************************************************************************************/
//谢谢牛友的提示，以下纯手写，望批评指正！！！
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<vector<int> > permutation(int n){
//全排列
vector<vector<int> > res;
vector<int> num(n);
for(int i=0;i<num.size();i++){
num[i]=i+1;
}
do{
res.push_back(num);
}while(next_permutation(num.begin(),num.end())); //如果知道这个next_permutation是库函数，是不是好做很多，不知道的是因为leetcode没刷好
return res;
}
void finduse(vector<vector<int> > &res,vector<int> data){
//找出满足看的清的数字的所有序列
for(int i=0;i<res.size()-1;i++){
for(int j=0;j<data.size();j++){
if(data[j]!=res[i][j]&&data[j]!=0){
res.erase(res.begin()+1);
i--;
break;
}
}
}
}
int findsum(vector<vector<int> > res,int k){
//找到满足k个有序对的所有序列，计算这样序列的个数
int ll=res.size();
int l=(*res.begin()).size();
int count=0;
for(int i=0;i<ll;i++){
int sum=0;
for(int j=0;j<l-1;j++){
for(int s=j+1;s<l;s++){
if(res[i][j]<res[i][s])
sum++;
}
}
if(sum==k)
count++;
}
return count;
}
int main(){
int n;
int k;
while(cin>>n>>k){
if(n<=0||n>100)
break;
vector<int> data(n);
for(int t=0;t<n;t++){
cin>>data[t];
vector<vector<int> > res = permutation(n);
finduse(res,data);
int count = findsum(res,k);
cout<<count<<endl;
}
return 0;
}
微软公司福利 56人发布