[编程题]数列还原
- 热度指数：14898 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10
个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。
输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。
输出描述:
输出一行表示合法的排列数目。
示例1
输入
5 5 4 0 0 2 0
输出
2
思路：首先将模糊的数字统计出来，并求出这些数字的全排列，然后对每个排列求顺序对
关键去求全排列，需要递归的求出所有排列。。。
ps：第一次做的时候没看清楚题，以为可以有重复数字，直接深搜计算了，结果。。。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main{
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int RES = 0;
int n = sc.nextInt();
int k = sc.nextInt();
int[] A = new int[n];
boolean[] flag = new boolean[n+1];
//flag标记哪些数字已经存在
for(int i=0;i<n;i++){
A[i] = sc.nextInt();
if(A[i] != 0){
flag[A[i]] = true;
}
}
//统计排列中不存在的数字
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=1;i<=n;i++){
if(flag[i] == false)
list.add(i);
}
//perm用来存模糊数字的全排列
List<ArrayList<Integer>> perm = new ArrayList<ArrayList<Integer>>();
//计算perm
calperm(perm, list, 0);
//统计已有的排列的顺序对
int cv = 0;
for(int i=0;i<n;i++){
if(A[i]!= 0){
for(int j=i+1;j<n;j++){
if(A[j] != 0 && A[i] < A[j])
cv++;
}
}
}
//计算每个模糊数字排列的顺序对，如果与k相等，则结果RES加一
for(ArrayList<Integer> tmp : perm){
int val = cv;
int[] tmpA = Arrays.copyOf(A, n);
val += calvalue(tmp, tmpA);
if(val == k)
RES++;
}
System.out.println(RES);
}
}
//计算排列的顺序对
public static int calvalue(List<Integer> list, int[] A){
int val = 0;
int j = 0;
for(int i=0;i<A.length;i++){
if(A[i] == 0){
A[i] = list.get(j++);
for(int k = 0;k<i;k++){
if(A[k]!=0 && A[k]<A[i])
val++;
}
for(int k=i+1;k<A.length;k++){
if(A[k]!=0 && A[k]>A[i])
val++;
}
}
}
return val;
}
//计算全排列
public static void calperm(List<ArrayList<Integer>> perm , ArrayList<Integer> list, int n){
if(n == list.size()){
perm.add(new ArrayList<Integer>(list));
}else{
for(int i=n;i<list.size();i++){
Collections.swap(list, i, n);
calperm(perm, list, n+1);
Collections.swap(list, i, n);
}
}
}
}
发表于 2016-08-11 14:54:23
回复(9)
先统计哪些数没出现，哪些位置缺少数值。
然后考虑计算。
10!=3628800
如果是每种排列还暴力计算（~100*100），这不行，太慢了
考虑预先计算一部分。
总顺序对数=已经填进去的数之间的顺序对数+没有填进去的数之间的顺序对数+已经填进去和没有填进去的数之间的顺序对数
第一部分：预先算一遍就好了
第二部分：只有10*10，暴力计算
第三部分：预先处理，每个数填在空位上，和其他预先填进去的数组成的顺序对数
三部分相加，判断等不等于k就行。
计算量？
10*10+10，也就110
所以你看，<1ms过了
（呃，其实数据太弱有关系吧）
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
//http://www.nowcoder.com/questionTerminal/b698e67a2f5b450a824527e82ed7495d
int a[105];
bool appear[105];
int missidx[15];
int missnum[15];
int misscnt=0;
int smaller[105][105];
int larger[105][105];
int calc_orderedPairs(int *num,int n){
int ans=0;
for(int i=1;i<n;i++){
if(num[i])
for(int j=0;j<i;j++){
if(num[j]&&num[j]<num[i]){
++ans;
}
}
}
return ans;
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
if(k>n*(n-1)/2){
puts("0");
return 0;
}
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(!a[i])missidx[misscnt++]=i;
else appear[a[i]]=1;
}
misscnt=0;
for(int i=1;i<=n;i++){
if(!appear[i]){
missnum[misscnt++]=i;
}
}
//given inner
int given=calc_orderedPairs(a,n);
if(given>k){
puts("0");
return 0;
}
//given and not given
for(int i=0;i<misscnt;++i){
int small=0,large=0;
for(int j=0;j<n;j++){
if(!a[j]){
smaller[j][missnum[i]]=small;
}
else if(a[j]<missnum[i])++small;
}
for(int j=n-1;j>=0;--j){
if(!a[j]){
larger[j][missnum[i]]=large;
}
else if(a[j]>missnum[i])++large;
}
}
int ans=0;
//not given
do{
int inner=calc_orderedPairs(missnum,misscnt);
for(int i=0;i<misscnt;++i){
inner+=smaller[missidx[i]][missnum[i]];
inner+=larger[missidx[i]][missnum[i]];
}
if(inner+given==k) ++ans;
}while(next_permutation(missnum,missnum+misscnt));
printf("%d\n",ans);
return 0;
}
发表于 2016-08-07 12:32:13
回复(3)
将被模糊掉的数字进行全排列，然后将全排之后的数字放进原序列，统计顺序对。代码如下：
#include<iostream>
#include<vector>
using namespace std;
bool find(vector<int> v,int n) //查询v中是否存在整数n
{
for(int i = 0;i<v.size();++i)
if(v[i]==n)
return true;
return false;
}
vector<vector<int>> pv; //全局变量
void Perm(vector<int> &v,int st) //对v中的数字进行全排列
{
if(st == v.size())
pv.push_back(v);
else
{
for(int i = st;i<v.size();++i)
{
swap(v[i],v[st]);
Perm(v,st+1);
swap(v[i],v[st]);
}
}
}
void change(vector<int> &v,vector<int> subv,vector<int> vpos)//将v中的0用全排之后的数字分别代替
{
for(int i = 0;i<vpos.size();++i)
v[vpos[i]] = subv[i];
}
int cal(vector<int> v) //计算顺序对的个数
{
int cnt = 0;
for(int i = 0;i<v.size()-1;++i)
for(int j = i+1;j<v.size();++j)
if(v[i]<v[j])
++cnt;
return cnt;
}
int main()
{
int n,k,tmp;
while(cin>>n>>k)
{
vector<int> v,subv,vpos;
for(int i = 0;i<n;++i)
{
cin>>tmp;
v.push_back(tmp);
}
for(int i = 0;i<v.size();++i)
if(v[i]==0)
vpos.push_back(i); //记录下vector<int>中0的位置
for(int i = 1;i<=n;++i)
if(!find(v,i))
subv.push_back(i);
Perm(subv,0);
vector<int> vcnt;
for(int i = 0;i<pv.size();++i)
{
change(v,pv[i],vpos);
vcnt.push_back(cal(v));
}
int vcntk = 0;
for(int i = 0;i<vcnt.size();++i)
if(vcnt[i]==k)
++vcntk;
cout<<vcntk<<endl;
}
return 0;
}
编辑于 2016-08-09 16:23:45
回复(6)
#include<stdio.h>
int a[20],tot=0,book[101],n,x[101],res=0,k,i,vis[20];
int getCnt(){
int i,j,res=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(x[i]<x[j]) res++;
return res;
}
void dfs(int step){
if(step==n){
if(getCnt()==k) res++;
return;
}
if(x[step]) dfs(step+1);
else
for(int i=0;i<tot;i++)
if(!vis[i]){
vis[i]=1,x[step]=a[i];
dfs(step+1);
vis[i]=0,x[step]=0;
}
}
int main(){
for(scanf("%d%d",&n,&k),i=0;i<n;i++)
scanf("%d",&x[i]),book[x[i]]=1;
for(i=1;i<=n;i++)
if(!book[i]) a[tot++]=i;
dfs(0);
printf("%d\n",res);
}
发表于 2017-10-21 00:24:45
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int n,k;
while(cin >> n >> k)
{
int *data = new int[n];
bool *flag0 = new bool[n];
int num0 = 0;
for(int i=0; i<n; i++)
{
cin >> data[i];
if(data[i] == 0) num0 ++, flag0[i] = true;
else flag0[i] = false;
}
int *data2 = new int[num0];
int pos = 0;
for(int i=1; i<=n; i++)
{
int j;
for(j=0; j<n; j++) if(data[j] == i) break;
if(j == n) data2[pos++] = i;
}
int num_k;
int result = 0;
do{
pos = 0;
num_k = 0;
for(int i=0; i<n; i++) if(flag0[i]) data[i] = data2[pos++];
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++) if(data[j] > data[i]) num_k ++;
}
if(num_k == k) result ++;
}while(next_permutation(data2,data2+num0));
cout << result << endl;
}
return 0;
}
发表于 2017-08-17 20:39:40
回复(1)
import itertools
import copy
n,k=map(int,input().split())
A=list(map(int,input().split()))
def findpair(list):
num=0
for i in range(len(list)):
t=0
for j in range(i+1,len(list)):
if list[i]<list[j]:
t+=1
num+=t
return num
a=[]
for p in range(1,n+1):
if p not in A:
a.append(p)
b=list(itertools.permutations(a,len(a)))
y=0
for u in range(len(b)):
B=copy.deepcopy(A)
e=0
for w in range(n):
if B[w]==0:
B[w]=b[u][e]
e+=1
r=findpair(B)
if r==k:
y+=1
print(y)
小白刚学
发表于 2017-08-16 12:44:23
回复(0)
穷举
先找出缺失的数字，利用递归求取它们的全排列；然后遍历全排列的结果，将缺失数字的每一种排列填入原数组计算空值充填完之后的数组顺序对，顺序对等于k就自增计数。
def permutation(nums, p, q, candicates): if p == q: candicates.append(list(nums)) else: for i in range(p, q): nums[i], nums[p] = nums[p], nums[i] permutation(nums, p + 1, q, candicates) nums[i], nums[p] = nums[p], nums[i] def computePairs(nums): n, cnt = len(nums), 0 for i in range(n - 1): for j in range(i + 1, n): if nums[i] < nums[j]: cnt += 1 return cnt if __name__ == "__main__": n, k = map(int, input().split()) nums = list(map(int, input().split())) normal = [num for num in nums if num != 0] # 未缺失数字 missing = list(set(range(1, n + 1)) - set(normal)) # 缺失数字 missCnt = len(missing) candicates = [] permutation(missing, 0, missCnt, candicates) # 缺失数字的全排列 count = 0 for candicate in candicates: # 把缺失数字填入原数组 arr = list(nums) ptr = 0 for i in range(n): if nums[i] == 0: arr[i] = candicate[ptr] ptr += 1 else: arr[i] = nums[i] # 暴力计算顺序对 if computePairs(arr) == k: count += 1 print(count)
数据量比较小，直接暴力O(N2)计算顺序对数目就行，也可以按照归并排序的思路，用O(NlogN)的时间复杂度计算顺序对数目。
发表于 2022-01-08 16:56:30
回复(0)
只通过了80%，有一处小错误，我实在找不出来了，思想是对的。找出缺少的数
字，将其全排序，然后在放回原数组中，判断该数组是否成立，成立加一
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
int n=input.nextInt();
int k=input.nextInt();
int[] a=new int[n];
for(int i=0; i<n; i++)
a[i]=input.nextInt();
boolean[] f=new boolean[n];
for(int i=0; i<n; i++){
if(a[i]!=0){
f[a[i]-1]=true;
}
}
TreeSet<String> arr=new TreeSet<>();
String s="";
for(int i=0; i<n; i++){
if(!f[i])
s+=String.valueOf(i+1);
}
arr.add(s);
isPiont(0,s.toCharArray(),arr);
int count=0;
for(String elem: arr){
int[] temp=new int[n];
int index=0;
for(int i=0; i<n; i++){
if(a[i]==0){
temp[i]=Integer.valueOf(String.valueOf(elem.charAt(index++)));
}else{
temp[i]=a[i];
}
}
if(isRight(k,n,temp))
count++;
}
System.out.println(count);
}
}
public static boolean isRight(int k, int n, int[] a){
int count=0;
for(int i=0; i<n-1; i++){
for(int j=i+1; j<n; j++){
if(a[i]<a[j])
count++;
}
}
if(count==k)
return true;
else
return false;
}
public static void isPiont(int start, char[] ch, TreeSet<String> arr){
if(start==ch.length-1){
arr.add(String.valueOf(ch));
return ;
}else{
for(int i=start; i<ch.length; i++){
swap(i, start, ch);
isPiont(start+1,ch,arr);
swap(i, start, ch);
}
}
}
public static void swap(int i, int j, char[] ch){
char temp=ch[i];
ch[i]=ch[j];
c***emp;
}
}
编辑于 2018-09-03 20:19:24
回复(0)
import itertools
list1 = input().split()
n = int(list1[0])
k = int(list1[1])
A = input().split()
B = []
for i in range(n):
B.append(int(A[i]))
zero_ind = []
not_zero = []
# 找出零的位置与非零元素的值
for i in range(n):
if B[i] == 0:
zero_ind.append(i)
else:
not_zero.append(i)
# 求出剩下需要填入数组的值
num_to_add = list(range(1,n+1))
for i in range(len(not_zero)):
num_to_add.remove(B[not_zero[i]]) #1
dict1 = {}
j = 0
# 排列
for i in itertools.permutations(num_to_add,len(num_to_add)):
dict1[j] = list(i)
j += 1
con_right = 0
# 填入数组与求顺序
for i in range(len(dict1)):
#i=0
test = dict1[i]
con = 0
for m in range(len(num_to_add)):
B.insert(zero_ind[m],test[m])
del B[zero_ind[m]+1]
for x in range(n):
for y in range(x+1,n):
if (B[x] < B[y]):
con += 1
if (con == k):
con_right += 1
print(con_right)
新手上路，python编写，欢迎大家指导
发表于 2018-08-06 08:40:54
回复(0)
# -*- coding: utf8 -*-
import itertools
def get_ppair_num(a, n,dvalues):
"""
计算用dvalues替换a中对应0元，计算替换后的顺序对数
"""
idx = 0
count = 0
for i in range(n):
if a[i] == 0:
value = dvalues[idx]
idx += 1
else:
value = a[i]
idx0=0
for j in range(i):
if a[j]==0:
dv=dvalues[idx0]
idx0+=1
else:
dv=a[j]
if value > dv:
count += 1
return count
def count_permuations(a, n, k):
"""
枚举所有0元位置的一个全排列,统计每种顺序对数为k的排列
"""
count = 0
s = set(range(1, n + 1)) - set(a)
for dvalues in itertools.permutations(s):
ct=get_ppair_num(a, n,dvalues)
if ct==k:
count += 1
return count
n, k = map(int, raw_input().strip().split(' '))
a = map(int, raw_input().strip().split(' '))
print count_permuations(a, n, k)
发表于 2018-07-31 16:39:20
回复(0)
暴力解法
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int n, k,totalLegal=0;
vector<int> A, B;
vector<int> indexRem, remainMat;
int calcK(vector<int> vec){
int count = 0;
for (int i = 0; i < vec.size(); i++){
for (int j = i + 1; j < vec.size(); j++){
if (vec[i] < vec[j]){
count++;
}
}
}
return count;
}
void allSort(vector<int> vec, int index){
if (index == vec.size()){
for (int i = 0; i < indexRem.size(); i++){
B[indexRem[i]] = vec[i];
}
if (k == calcK(B)){
totalLegal++;
}
return;
}
else{
for (int i = index; i < vec.size(); i++){
swap(vec[i], vec[index]);
allSort(vec, index + 1);
swap(vec[i], vec[index]);
}
}
}
int main(){
cin >> n>>k;
A=vector<int>(n, 0);
B = A;
for (int i = 0; i < n; i++){
A[i] = i + 1;
};
for (int j = 0; j < n; j++){
cin >> B[j];
}
//得到看不清索引的下标
for (int i = 0; i < n; i++){
if (B[i] != 0){
A[B[i]-1]=0;
}else{
indexRem.push_back(i);
}
}
//得到看不清的项
for (int i = 0; i < n; i++){
if (A[i] != 0){
remainMat.push_back(A[i]);
}
}
//得到缺失项的全排列
allSort(remainMat, 0);
cout << totalLegal << endl;
return 0;
}
编辑于 2018-07-23 20:22:52
回复(0)
有没有大佬能帮我看看我的代码，实在找不到问题出在哪。。。
case通过率为90.00%
测试用例:
100 2405
4 62 10 33 86 58 9 49 68 84 30 88 90 67 59 0 19 25 12 72 44 85 51 5 13 98 94 91 24 47 27 95 100 77 15 92 0 70 55 31 28 81 75 39 34 74 2 89 45 63 36 64 43 93 29 50 7 54 0 82 71 66 97 53 23 38 69 52 48 21 26 17 20 57 37 61 11 73 60 78 18 79 0 80 16 83 56 35 0 32 6 96 1 99 46 76 22 87 3 41
对应输出应该为:
1
你的输出为:
2
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
#include<climits>
#include<set>
using namespace std;
void process(vector<int> array, int n, int k)
{
set<int> sets;
for (int i = 0; i < n; i++)
{
if (array[i] != 0)
{
sets.insert(array[i]);
}
}
vector<int> num; //存放缺损元素
for (int i = 1; i < n + 1;i++)
{
if (sets.find(i) == sets.end())
{
num.push_back(i);
}
}
int res = 0;
vector<int> arr;
do
{
int index = 0;
int count = 0;
for (int i = 0; i < n; i++)
{
int cur = array[i] == 0 ? num[index++] : array[i];
arr.push_back(cur);
for (int j = 0;j < i;j++)
{
if (arr[j] < cur)
{
count++;
//cout << count << endl;
}
}
}
res += count == k ? 1 : 0;
} while (next_permutation(num.begin(), num.end()));
cout << res << endl;
}
int main()
{
int n, k;
cin >> n >> k;
vector<int> array(n, 0);
for (int i = 0; i < n;i++)
{
cin >> array[i];
}
process(array, n, k);
system("pause");
return 0;
}
发表于 2018-04-06 12:37:44
回复(0)
//x的，这编辑工具真难用
//dfs枚举每一个组合，对于每一个组合都计算一次顺序数对个数，注意在枚举的是就可以计算，顺便可以剪枝
import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int ans = 0;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] arr = lineToIntArray(br.readLine());
int n = arr[0], k = arr[1];
arr = lineToIntArray(br.readLine());
List<Integer> positions = new LinkedList<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
set.add(arr[i]);
if (arr[i] == 0) { positions.add(i); continue;}
for (int j = i + 1; j < n; j++) {
if (arr[j] == 0) continue;
if (arr[i] < arr[j]) k--;
}
}
List<Integer> loss = new LinkedList<>();
for (int i = 1; i <= n; i++) if (!set.contains(i)) loss.add(i);
dfs(arr, positions, k, loss, 0);
System.out.println(ans);
}
public static void dfs(int[] arr, List<Integer> positions, int k, List<Integer> number, int depth) {
if (k == 0 && number.size() == 0) {ans++; return;}
if (k < 0 || depth >= positions.size()) return;
int pos = positions.get(depth);
for (int i = 0; i < number.size(); i++) {
int num = number.remove(i);
arr[pos] = num;
dfs(arr, positions, k - countPair(arr, pos), number, depth + 1);
arr[pos] = 0;
number.add(i, num);
}
}
public static int countPair(int[] arr, int pos) {
int ans = 0;
for (int i = 0; i < pos; i++) {
if (arr[i] > 0 && arr[i] < arr[pos]) ans++;
}
for (int i = pos + 1; i < arr.length; i++) {
if (arr[i] > 0 && arr[pos] < arr[i]) ans++;
}
return ans;
}
public static int[] lineToIntArray(String line) {
String[] arr = line.trim().split(" ");
int[] ans = new int[arr.length];
for (int i = 0; i < arr.length; i++)
ans[i] = Integer.parseInt(arr[i]);
return ans;
}
public static int lineToInt(String line) {
return Integer.parseInt(line);
}
}
编辑于 2018-04-03 20:00:42
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int order(vector<int> vi){ int cnt=0; if(vi.size()>=2){ for(int i=vi.size()-1;i>=0;i--){ for(int j=0;j!=i;j++){ if(vi[i]>vi[j]) cnt++; } } } return cnt;
}
int main(){
int n,k;
while(cin>>n>>k){
int cnt=0;
vector<int> pst0;
vector<int> a(n,0);
vector<int> c; vector<bool> flag(n+1,false);
for(int i=0;i<a.size();i++){
cin>>a[i];
if(a[i]!=0){
flag[a[i]]=true; }else{ pst0.push_back(i); }
}
for(int i=1;i<flag.size();i++){
if(flag[i]==false){
c.push_back(i);
}
}
sort(c.begin(),c.end());
/* for(int i:c){
cout<<i<<" "; }cout<<endl; for(int i:pst0){ cout<<i<<" "; }cout<<endl;
*/ do{ int idx=0; for(int i=0;i<pst0.size();i++){ a[pst0[i]]=c[idx]; idx++; } int tmp=order(a);
/* for(int i:a){ cout<<i<<" "; }cout<<": "<<tmp<<endl;
*/ if(tmp==k) cnt++; }while(next_permutation(c.begin(),c.end())); cout<<cnt<<endl;
}
}
发表于 2017-09-21 15:38:42
回复(0)
#include<iostream>
#include<vector>
#include<set>
#include <algorithm>
using namespace std;
int find_dui(int a[], int N){
int pairnum = 0;
for (int i = 0; i < N-1; ++i){
for (int j = i+1; j < N; ++j)
{
if (a[i] < a[j])
pairnum++;
}
}
return pairnum;
}
int main()
{
int N, K;
int num = 0;
cin >> N >> K;
int a[100];
vector <int> s;
vector<int> fuzpos;
vector<int> fuznum;
for (int i = 0; i < N; ++i)
{
cin >> a[i];
s.push_back(a[i]);
if (a[i] == 0)
fuzpos.push_back(i); // missing num position
}
for (int i = 1; i <= N; ++i)
if (find(s.begin(), s.end(), i) == s.end())
fuznum.push_back(i); // 没有出现过的数字
vector<int> ::iterator iter = fuznum.begin();
do
{
for (int k = 0; k < fuznum.size(); ++k)
a[fuzpos[k]] = fuznum[k];
if (find_dui(a, N) == K)
num++;
} while (next_permutation(iter, iter + fuznum.size())); // 取下一个排列组合
cout << num << endl;
}
发表于 2017-09-01 20:45:38
回复(0)
用的最直接的方法遍历所有没出现数字的全排列，并将各种排列方式根据索引添加在0位置上 再遍历每一种的合法排序数目，与k相等计数器count++
import java.util.LinkedList;import java.util.List;import java.util.Scanner;public class Main{static List<List<Integer>> resultlist=new LinkedList<List<Integer>>();//最后得到各种组合的链表public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int k=scan.nextInt();int []nums=new int[n];for (int i = 0; i < n; i++) {nums[i]=scan.nextInt();}int zeros=getzerocount(nums);List<Integer> list=getnums(nums);//存在的数字List<Integer> old_list=ArrayToList(nums);List<Integer> zero_index=getindexofzero(nums);//零索引的链表List<Integer> numbers=get_no_nums(nums);// System.out.print("oldList");printList(old_list);// System.out.print("zeroList");printList(zero_index);// System.out.print("list");printList(list);// System.out.print("numbers");printList(numbers);int x[]=new int[numbers.size()];for (int i = 0; i < x.length; i++) {x[i]=0;}dfs(ListtoArray(numbers), x);// System.out.print("oldList");printList(old_list);// System.out.print("zeroList");printList(zero_index);// System.out.print("list");printList(list);//System.out.println(resultlist.size());int count=0;for (int i = 0; i < resultlist.size(); i++) {//第几条返回记录List<Integer> new_list=old_list;List<Integer> eachlist=resultlist.get(i);for (int j = 0; j < zeros; j++) {new_list.set(zero_index.get(j), eachlist.get(j));}// printList(new_list);if(getcount(new_list)==k){count++;}}System.out.println(count);}private static int [] ListtoArray(List<Integer> list){int x[]=new int[list.size()];for (int i = 0; i < list.size(); i++) {x[i]=list.get(i);}return x;}private static List<Integer> getindexofzero(int a[]){//获得数字0位置的索引List<Integer> list=new LinkedList<Integer>();for (int i = 0; i < a.length; i++) {if(a[i]==0){list.add(i);}}return list;}@SuppressWarnings("null")private List<Integer> getUnuseNums(int nums[],int n){List<Integer> list=getnums(nums);List<Integer> list2=null;for (int i = 1; i <=n; i++) {if(list.contains(i)){continue;}else{list2.add(i);}}return list2;}private static int getzerocount(int []a){int n=a.length;return n-getnums(a).size();}private static void printList(List<Integer> list){for (int i=0;i<list.size();i++) {System.out.print(list.get(i)+" ");}System.out.println();}private static List<Integer> ArrayToList(int a[]){List<Integer> list=new LinkedList<Integer>();for (int i = 0; i < a.length; i++) {list.add(a[i]);}return list;}static int depth=0;private static void dfs(int numbers[],int [] list){if(depth==numbers.length){depth=depth-1;if(!charge(list))//printList(ArrayToList(list));resultlist.add(ArrayToList(list));return;}for (int i = 0; i < numbers.length; i++) {// System.out.println("depth="+depth);list[depth++]=numbers[i];dfs(numbers,list);}depth--;return;}private static boolean charge(int nums[]){for (int i = 0; i < nums.length; i++) {for (int j = i+1; j < nums.length; j++) {if(nums[i]==nums[j]){return true;}}}return false;}private static int getcount(List list){/*** 计算合法排列个数* */int count=0;for (int i = 0; i < list.size(); i++) {for (int j = i+1; j < list.size(); j++) {int temp1=(Integer) list.get(i);int temp2=(Integer) list.get(j);if(i<j&&temp1<temp2){count++;}}}return count;}private static List<Integer> getnums(int nums []){/** 把含零数组中非零元素提取出来转换为list* **/List<Integer> list = new LinkedList<Integer>();for (int i = 0; i < nums.length; i++) {if(nums[i]!=0)list.add(nums[i]);}return list;}private static List<Integer> get_no_nums(int nums []){/** 把含零数组中非零元素提取出来转换为list* **/List<Integer> list1=ArrayToList(nums);List<Integer> list = new LinkedList<Integer>();for (int i = 1; i <= nums.length; i++) {if(list1.contains(i))continue;else list.add(i);}return list;}}
发表于 2017-09-01 15:42:34
回复(0)
import java.util.Scanner;
import java.util.ArrayList;
//从数列的第一位开始递归，遇到0要尝试所有可能的数（回溯）
//遇到非0则只计算当前位置之前的顺序对数，然后继续下一位
//注意：每次回溯要更新list和count
public class Main{
private static ArrayList<Integer> list = new ArrayList<>();
private static int count = 0; //顺序对对数
private static int num = 0; //符合条件的排列数目
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int n = in.nextInt();
int k = in.nextInt();
ArrayList<Integer> tempList = new ArrayList<>();
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = in.nextInt();
tempList.add(arr[i]);
}
for(int i = 1; i <= n; i++){
if(!tempList.contains(i)){
list.add(i);
}
}
permutation(arr, 0, k);
System.out.println(num);
}
}
private static void permutation(int[] arr, int index, int k){
if(index >= arr.length){
return;
}
if(arr[index] == 0){
for(int i = 0; i < list.size(); i++){
arr[index] = list.remove(i);
int pairs = calc(arr, index);
count += pairs;
if(index == arr.length-1 && count == k){
num++;
}
permutation(arr, index+1, k);
count -= pairs;
list.add(i, arr[index]);
arr[index] = 0;
}
}else{
int pairs = calc(arr, index);
count += pairs;
if(index == arr.length-1 && count == k){
num++;
}
permutation(arr, index+1, k);
count -= pairs;
}
}
private static int calc(int[] arr, int index){
int cnt = 0;
for(int i = 0; i < index; i++){
if(arr[i] < arr[index])
cnt++;
}
return cnt;
}
}
发表于 2017-08-10 17:15:49
回复(0)
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Main {
/**
*如果给我们一个序列（不含有任何未知的元素），我们可以通过两次循环获取有多少个顺序对。
*但是如果插入一个未知元素，顺序对变化了多少呢？等于这个元素与前面元素的新增的顺序对，和后面比较的新增的顺序对。
*如果插入多个呢？可以逐次插入，让每次只有一个位置插入元素，其他未知临时忽略就可以了。这样就能递归解决问题。
*一个序列的总的顺序对，等于插入前的对数，加上逐次插入未知产生的对数。
*总的合法排列就等于未知数排列的合法排列数。
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] arrInput = br.readLine().trim().split(" ");
int n = Integer.parseInt(arrInput[0]);
int k = Integer.parseInt(arrInput[1]);
int[] arrNum = new int[n];
int knownedSeqPair = 0;
ArrayList<Integer> listIndex = new ArrayList<Integer>();//记住模糊位置的索引
ArrayList<Integer> listBlur = new ArrayList<Integer>();//记住模糊数字
HashSet<Integer> setBook = new HashSet<Integer>();//找到模糊数字的工具
arrInput = br.readLine().trim().split(" ");
for (int i=0; i<arrInput.length; i++) {
arrNum[i] = Integer.parseInt(arrInput[i]);
if (arrNum[i] == 0) {//模糊的记住位置,用于擦除数据
listIndex.add(i);
} else {//不模糊的记住数据本身，用于找到模糊的数据
setBook.add(arrNum[i]);
}
}
for (int i=1; i<=n; i++) {//查找模糊的数字
if (false == setBook.contains(i)) {
listBlur.add(i);
}
}
for (int i=0; i<arrNum.length; i++) {
if (arrNum[i] != 0) {//不能是模糊数字
for (int j=i+1; j<arrNum.length; j++) {
if (arrNum[j] != 0 && arrNum[i] < arrNum[j]) {//不能是模糊数字
knownedSeqPair++;
}
}
}
}
System.out.println(Main.getSeqNum(arrNum, listBlur, listIndex, knownedSeqPair, 0, k));
}
public static int getSeqNum(int[] arrNum, ArrayList<Integer> listBlur, ArrayList<Integer> listIndex, int knownedSeqPair, int n, int k) {
int result = 0;
if (n == listBlur.size()) {//子排列已经出现
int sumSeqNum = knownedSeqPair;
int i = 0;
int j = 0;
for (i=0; i<listBlur.size(); i++) {//计算新增的排列
for (j=0; j<arrNum.length && arrNum[j] != 0; j++) {//前半部分
if (arrNum[j] < listBlur.get(i)) {
sumSeqNum++;
}
}
if (j < arrNum.length) {//插入，为下次会比较，判断是为了应对根本没有未知的情况
arrNum[j++] = listBlur.get(i);
}
for (; j<arrNum.length; j++) {//比较后面
if (arrNum[j] != 0 && arrNum[j] > listBlur.get(i)) {
sumSeqNum++;
}
}
}
for (i=0; i<listIndex.size(); i++) {//擦除模糊数字的排列，用于下次
arrNum[listIndex.get(i)] = 0;
}
if (sumSeqNum == k) {
result = 1;
}
} else {
for (int i=n; i<listBlur.size(); i++) {//其实等于n是因为不交换（自交换）也是一种情况。
Collections.swap(listBlur, n, i);
result += Main.getSeqNum(arrNum, listBlur, listIndex, knownedSeqPair, n+1, k);
Collections.swap(listBlur, n, i);
}
}
return result;
}
}
发表于 2018-11-03 14:55:12
回复(0)
//方法是牛客网---hofighter提供的，个人只是加了一些注释,方便自己和大家理解
/**思路：首先将模糊的数字统计出来，并求出这些数字的全排列，然后对每个排列求顺序对
关键去求全排列，需要递归的求出所有排列。。。
ps：第一次做的时候没看清楚题，以为可以有重复数字，直接深搜计算了，结果。。。*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main{
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int RES = 0;
int n = sc.nextInt();
int k = sc.nextInt();
int[] A = new int[n];
boolean[] flag = new boolean[n+1];//为什么是 n+1?因为n是从1开始的,必须有flag[n]
//flag标记哪些数字已经存在
for(int i=0;i<n;i++){
A[i] = sc.nextInt();
if(A[i] != 0){
flag[A[i]] = true;
}
}
//统计排列中不存在的数字
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=1;i<=n;i++){
if(flag[i] == false)
list.add(i);
}
//perm用来存模糊数字的全排列
List<ArrayList<Integer>> perm = new ArrayList<ArrayList<Integer>>();
//计算perm
calperm(perm, list, 0);
//统计已有的排列的顺序对
int cv = 0;
for(int i=0;i<n;i++){
if(A[i]!= 0){
for(int j=i+1;j<n;j++){
if(A[j] != 0 && A[i] < A[j])
cv++;
}
}
}
//计算每个模糊数字排列的顺序对，如果与k相等，则结果RES加一
for(ArrayList<Integer> tmp : perm){
int val = cv;
int[] tmpA = Arrays.copyOf(A, n);
val += calvalue(tmp, tmpA);
if(val == k)
RES++;
}
System.out.println(RES);
}
}
/**
* 计算排列的顺序对
* @param list 模糊数列的某个排列
* @param A 最终的某个排列
*/
public static int calvalue(List<Integer> list, int[] A){
int val = 0;
int j = 0;
for(int i=0;i<A.length;i++){
if(A[i] == 0){
A[i] = list.get(j++);//每一一个为0的位置 安插一个list中的数字
for(int k = 0;k<i;k++){
if(A[k]!=0 && A[k]<A[i])
val++;
}
for(int k=i+1;k<A.length;k++){
if(A[k]!=0 && A[k]>A[i])
val++;
}
}
}
return val;//最后返回时因为必须报list中的所有数据安插在为0的位置上
}
/**
* 计算全排列
* @param perm
* @param list 排列中不存在的数字
* @param n 初始为0
*/
public static void calperm(List<ArrayList<Integer>> perm , ArrayList<Integer> list, int n){
if(n == list.size()){
perm.add(new ArrayList<Integer>(list));
}else{
for(int i=n;i<list.size();i++){
Collections.swap(list, i, n);
calperm(perm, list, n+1);
Collections.swap(list, i, n);
}
}
}
}
编辑于 2016-08-25 18:43:14
回复(0)
首先，顺序对的个数互不影响。也就是说，对于数组A来说，增加（插入）一个数字，其A的顺序对个数不变，所以新数组A+1的顺序对个数=数组A的顺序对+新插入的数字产生的顺序对.
进而推广到，增加c个数字，新数组A+c的顺序对=数组A的顺序对+数组c的顺序对+每个新插入的数字产生顺序对（共c个数字）。
所以，1）首先计算已经给出的数字共有arrbase个顺序对；
2）然后计算缺失的数字共有canbase个顺序对；
3）最后计算每个缺失的数字产生的顺序对；
对于2,3步骤，可以将缺失的数字（数组）进行全排列。
#include <bits/stdc++.h>
using namespace std;
int getorderpair(int arr[],int n,int num,int pos){
int sum=0;
for(int i=0;i<n;++i){
if (!arr[i]) continue;
sum+=((arr[i]<num && i<pos)||(arr[i]>num && i>pos));
}
return sum;
}
int getorderpairall(int arr[],int n){
int sum=0;
for(int i=0;i<n;++i){
if (!arr[i]) continue;
sum+=getorderpair(arr,n,arr[i],i);
}
return sum/2; // each pair cal twice.
}
int main(){
int arr[100],can[10]; // missing num
unordered_set<int> s;
for(int n,k,c,base,ans;cin>>n>>k;c=0,s.clear()){
for(int i=ans=0;i<n;++i){
cin>>arr[i];
s.insert(arr[i]);
}
for(int i=c=0;i<n;++i){ // find missing num
if (s.find(i+1)==s.end()) can[c++]=i+1;
}
int arrbase = getorderpairall(arr,n);
do{
int canbase = getorderpairall(can,c);
for(int i=base=0,j=0;i<n;++i){
if (arr[i]) continue;
base+=getorderpair(arr,n,can[j++],i);
}
if (arrbase+canbase+base==k) ++ans;
}while(next_permutation(can,can+c));
cout<<ans<<endl;
}
return 0;
}
发表于 2016-08-10 18:05:01
回复(2)
问题信息
通过挑战的用户
查看代码-
2022-09-06 21:40:53 -
2022-09-05 10:03:29 -
2022-08-30 20:17:03
-
2022-08-27 12:19:46
-
2022-08-26 14:18:17
相关试题
-
评论(4)
-
评论(333) 来自网易2017内推笔试编程...
-
评论(125) 来自网易2017内推笔试编程...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
