关注
回去想的,用全排列,逐个搜索
#include<stdio.h>
int p[4000000][100];//保存剩余数的全排列
int num=0;//保存剩余数全排列个数
int count=0;//保存i<j,a[i]<a[j]的个数
void swap(int &a,int &b)
{
int t;
t=a;
a=b;
b=t;
}
//求剩余数的个数
int less(int *a,int *b,int
n)//扫描b[n],如果有b[j]=a[i],b中从j开始每项往前面移一位 ,s记录b中剩余个数;
{
int i,j,k,s=n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(a[i]==0) break;
if(b[j]==a[i])
{
s--;
for(k=j;k<n-1;k++)
{
b[k]=b[k+1];
}
break;
}
}
return s;
}
//剩余的数全排列
void perm(int a[],int start,int
n)//a[n]数组从a[start]开始全排列,结果放在b[num][n]中 ,num计数
{
int i;
int *c;
if(start==n-1)
{
for(i=0;i<n;i++)
p[num][i]=a[i];
num++;
return;
}
else
{
for(i=start;i<n;i++)
{
swap(a[i],a[start]);
perm(a,start+1,n);
swap(a[i],a[start]);
}
}
}
//剩余排列数p[x][m]加到a[n]=0中
void add(int a[],int n,int x)
{
int i=0,j=0;
for(i=0;i<n;i++)
{
if(a[i]==0)
{
a[i]=p[x][j];
j++;
}
}
}
//计算是否k个 ,若是count++
void cou(int a[],int n,int k)
{
int i,j,c=0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a[i]<a[j])
c++;
}
if(c==k)
count++;
}
int main()
{
int n,k,m,i,j;
while(scanf("%d%d",&n,&k)!=EOF)
{
int a[n],b[n],c[n];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[i]=i+1;
}
m=less(a,b,n);
perm(b,0,m);
for(i=0;i<num;i++)
{
for(j=0;j<n;j++)
c[j]=a[j];
add(c,n,i);
cou(c,n,k);
}
printf("%d\n",count);
count=0;
num=0;
}
}
查看原帖
点赞 1
相关推荐
04-03 17:47
北京中南海业余大学 Java AI牛可乐:哇,听起来你很激动呢!杭州灵枢维度科技听起来很厉害呀~你逃课去白马培训,老冯会同意吗?不过既然你这么感兴趣,肯定是有原因的吧!
对了,想了解更多关于这家公司或者求职相关的问题吗?可以点击我的头像私信我哦,我可以帮你更详细地分析一下!
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 26届春招投递记录 #
51521次浏览 423人参与
# 薪资一样,你会选择去大厂还是小公司 #
34924次浏览 129人参与
# 27届实习投递记录 #
146887次浏览 1555人参与
# 哪个瞬间让你对大厂祛魅了? #
645480次浏览 4018人参与
# 实习的内耗时刻 #
242133次浏览 1664人参与
# 求职中的尴尬瞬间 #
41924次浏览 125人参与
# 记录实习开销 #
226450次浏览 1766人参与
# 你找工作的时候用AI吗? #
214547次浏览 1031人参与
# 听劝,这个简历怎么改 #
422791次浏览 1901人参与
# 春招 / 实习投递,你最焦虑的一件事 #
164622次浏览 1814人参与
# 暑假倒计时,你都干了些啥? #
62058次浏览 318人参与
# 机械人还在等华为开奖吗? #
344316次浏览 1658人参与
# 2022届毕业生现状 #
1174815次浏览 7802人参与
# 新凯来求职进展汇总 #
82560次浏览 194人参与
# 职场中那些令人叹为观止的八卦 #
112277次浏览 497人参与
# 华子oc时间线 #
1516149次浏览 7126人参与
# 牛友投递互助,不漏校招机会 #
494984次浏览 5368人参与
# 百度求职进展汇总 #
745438次浏览 6495人参与
# 大厂无回复,继续等待还是奔赴小厂 #
376180次浏览 2119人参与
# 正在实习的你,有转正机会吗? #
527867次浏览 3105人参与
查看30道真题和解析