|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 rockerz 于 2014-4-28 22:31 编辑
输入为N和C。你要把N个连续自然数任意排列。如果i在j前面,并且i>j,积分+1。问题要求积分必须等于C。输出有多少种排列方法。 0<=N<=1000 0<=C<=10,000
示例: 1432 积分为3, 因为 (4,3),(4,2),(3,2)。
示例输入1
10 1
示例输出1
9
示例输入2
4 3
示例输出2
6
我已经写了一个暴力的算法,但是暴力终究不是解决问题的办法。。N超过50时就有64位数不同的排列方法了。。然后再一一查看是否符合C,电脑肯定卡爆。
声明:这道题不是作业,不是考试题。是我出于爱好去尝试的。本人已经自己网上找过,但无法找到解题思路。
附上我的暴力解法。
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- int main()
- {
- int a[50];
- int n,c,count=0,solc=0;;
- scanf("%d %d",&n,&c);
- for (int i=0;i<n;i++){
- a[i]=i;
- }
- do {
- count=0;
- for (int i=0;i<n;i++){
- for (int j=i;j<n;j++){
- if (a[i]>a[j])count++;
- }
- if (count>c)break;
- }
- if (count==c)solc++;
- } while (next_permutation(a,a+n));
-
- printf("%d",solc);
- return 0;
- }
复制代码
|
|