N天以来关于变态比赛的研究~(效率有点慢)

哈哈 经过N天不懈的努力(好像都是玩了~~)终于对这个[变态比赛规则]程序算法有了一定的心得!!~~首先,介绍一下在网上搜到的高人的算法(听说这个题目的算法还不少,但是除了"暴力"递归的我认为在众多的程序中,这个写的比较好.复杂度要比光递归小了好多)

#include

int main(int argc, char *argv[])
{
int n, k;

/*if( argc!=3 )
{
printf("use: %s n k", argv[0]);
return -1;
}

n = atoi(argv[1]);
k = atoi(argv[2]);*/
scanf("%d %d",&n,&k); //input two numbers

if(foo(n, k)>0)
printf("YES\n");
else
printf("NO\n");

return 0;
}

int maxT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+(n-m)*(n-m-1)/2;
}

int minT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+minT(n-m, m);
}

int foo(int n, int k)
{
int max, min;
int m;

if( n<=0 n>500 k<0>n*(n-1)/2 )
return -1;

if( k==0 k==n-1)
return 1;

if( n==1 k0; m-- )
{
max = maxT(n, m);
min = minT(n, m);
if( k<=max &&amp;amp; k>=min )
{
if( foo(n-m, k-m*(n-m))>0 )
return 1;
}
}
return -1;
}

然后,再介绍一下我这几天的心得了.我就是在读这段程序时(呵呵,至今我还没有完全搞明白段代码是个什么意思~~ 那位高手来给点拨一下啊.谢谢!),基本上看懂一点,但是突然受到这段代码的启发,想到了一个算法.首先,我一开始是摸不着头脑,只是明白了按规则最多应该有N*(N-1)/2场比赛[每组一个人],最少应该有N-1场比赛[一组一个人,其他人一组].或者0场比赛[所有人一组].后来换个角度来考虑,觉得不应该从有K场比赛,如何分这N个人来考虑.应该考虑一下有N个人,如何分组才能有这K场比赛.另外,也不应该把所有人分在一组,然后分开一个,然后再一个...这样反倒没有规律了.后来想到如果一开始是每一个人一组,然后没人之间都有比赛这样就是一个完全无向图.而合并一组就是把组内的边除去.也就是m个人分为一组的话,就从N阶完全无向图中除去一个m阶完全无向图.
就这样一直合并直到能得到K条边为止,或者只能得到一个小于K的边数.至于具体的算法我还没写出来^_^!! 同时也不知道这个算法是否可行.拭目以待了^_^!!