关注
回去想的,用全排列,逐个搜索
#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
相关推荐
牛客热帖
更多
- 1... 🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端4.5W
- 2... 秋招应该侧重准备哪个部分的内容1.5W
- 3... 恋爱四年没想到过自己会出轨8248
- 4... 史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)7698
- 5... 其实主包早就找到工作了,但还是每天都刷7050
- 6... 离开软件测试才发现外面没有雨5371
- 7... 双非二本的漫漫游戏开发春招路Ver2.0——失业、感悟、再出发(万字长文)4961
- 8... 作为实习生,我问薪无愧4818
- 9... 25届毕业现在在家呆了一个多月,没工作4818
- 10... 从天坑文科到大二腾讯的经历4257
正在热议
更多
# 实习生的蛐蛐区 #
8528次浏览 68人参与
# 说说你知道的学历厂 #
3904次浏览 37人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
40448次浏览 291人参与
# 应届生,你找到工作了吗 #
6504次浏览 61人参与
# 秋招盘点:机械人值得去的企业 #
72908次浏览 671人参与
# 简历当中有水分算不算造假? #
7229次浏览 65人参与
# 双非应该如何逆袭? #
177402次浏览 3082人参与
# 你认为小厂实习有用吗? #
1743次浏览 27人参与
# 毕业旅行去哪玩儿 #
9143次浏览 127人参与
# 歌尔求职进展汇总 #
54786次浏览 335人参与
# 社会教会你的第一课 #
3259次浏览 58人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
117121次浏览 1134人参与
# 神州信息工作体验 #
12481次浏览 62人参与
# 三一集团提前批进度交流 #
23390次浏览 139人参与
# 非技术岗投递进展 #
145506次浏览 1264人参与
# 材料进Fab厂真的劝退吗? #
44241次浏览 184人参与
# 上班到公司第一件事做什么? #
62195次浏览 527人参与
# 百度工作体验 #
231742次浏览 2010人参与
# 数字马力求职进展汇总 #
179842次浏览 1489人参与
# 春招进度记录 #
344435次浏览 3351人参与
# 百度秋招提前批进度 #
106167次浏览 1124人参与