A25816. 组合
填空题
较难
知识点
题目描述
组合
题目描述
某校庆祝元旦，要求某班级选出n位男生和n位女生参加节目。由于节目需要，男女同学需要按照以下要求两两组合参加。
要求：
1.每组组合需为一位男生和一位女生；
2.一般情况，要求每组组合中男生身高大于等于女生身高；
3.特殊情况，可以出现女生身高大于男生身高的组合，但需要限定最多组合数。
在给出男生和女生数量n,和限定最多组合数k(1<n<10,0≤k<n),及所有男女生学身高后，按照组合要求共有多少种组合方案。
如：n为3(表示有3位男生和3位女生参加节目),k为0(表示组合中女生身高大于男生身高的组合情况最多出现0组),3位男生身高分别为165、175、163,3位女生身高分别为155、165、157。共有4种组合方案：
输入描述
第一行输入两个整数n和k(1<n<10,0≤k<n),n表示有n位男生和n位女生参加节目，k表示可以出现女生身高大于男生身高的最多组合数。
第二行输入n个正整数(130<正整数<200),表示n位男同学的身高，正整数之间一个空格隔开。
第三行输入n个正整数(130<正整数<200),表示n位女同学的身高，正整数之间一个空格隔开。
输出描述
输出一个整数，如果有满足要求的组合方案输出组合方案数，如果没有满足要求的组合方案输出0。
样例输入
3 0
165 175 163
155 165 157样例输出
4参考答案
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, k;
int by[15];
int gl[15];
int a[15];
int ans = 0;
int jie(int i) {
if (i == 0 || i == 1) {
return 1;
} else {
return i * jie(i - 1);
}
}
void check() {
int tmp = 0;
for (int i = 1; i <= n; ++i) {
if (by[i] < gl[a[i]]) {
tmp++;
}
if (tmp > k) {
return;
}
}
if (tmp <= k) {
ans++;
}
return;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> by[i];
}
for (int i = 1; i <= n; ++i) {
cin >> gl[i];
}
for (int i = 1; i <= n; ++i) {
a[i] = i;
}
int tt = jie(n);
for (int i = 1; i < tt; ++i) {
check();
next_permutation(a + 1, a + n + 1);
}
check();
cout << ans;
return 0;
}
上一题
下一题