关注
回去想的,用全排列,逐个搜索
#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
相关推荐
07-17 12:04
中国矿业大学 热设计工程师 点赞 评论 收藏
分享
07-02 10:39
门头沟学院 Java 
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 第一份工作应该选高薪还是热爱? #
66831次浏览 593人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92102次浏览 679人参与
# 秋招签约后的心态变化 #
82549次浏览 814人参与
# 听劝,这个公司值得去吗 #
486188次浏览 1700人参与
# 你觉得早上几点上班合适? #
72392次浏览 303人参与
# 学历贬值真的很严重吗? #
24497次浏览 174人参与
# 机械人与华为的爱恨情仇 #
120173次浏览 957人参与
# 一人推荐一个值得去的通信/硬件公司 #
186499次浏览 1859人参与
# 打工人的工作餐日常 #
53258次浏览 415人参与
# 哪些公司真双非友好? #
15840次浏览 82人参与
# 26届的你们有几段实习? #
44140次浏览 488人参与
# 月薪多少能在一线城市生存 #
28192次浏览 305人参与
# 双非能在秋招上岸吗? #
221742次浏览 1172人参与
# 你以为的实习VS真实的实习 #
29851次浏览 274人参与
# 今年秋招哪家公司给的薪资最良心? #
252964次浏览 1418人参与
# 你后悔自己读研吗? #
20652次浏览 240人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
117939次浏览 812人参与
# 追觅科技求职进展汇总 #
18269次浏览 120人参与
# 实习想申请秋招offer,能不能argue薪资 #
149960次浏览 932人参与
# 如何KTV领导 #
62802次浏览 472人参与