USACO Cowcycles

做这道题读懂题目很重要。这一句话可以直接说明题意——The problem wants you to find "an optimal set of gear ratios" such that the spacing between the ratios is most uniform.

USACO上介绍过解决问题的两个思路：1)generator 2)filter

对于这一题，generator比较难想出解决思路（本人想了近一周），因此选用filter，对于这一题，显然就是DFS了。

DFS呢，也没有什么好剪枝的，直接按顺序搜出所有情况，然后用一个函数检验是否满足约束条件，接着计算传动比，相邻比例的差值和差值的方差就可以了。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int tmp[2][100] = {};
int answer[2][100];
double minv = 100000000.0;
double ratio[3000];
double ratio_diff[3000];
int F,R;
int fb,fe,rb,re;

int cmp(const void *a,const void *b)
{
    return (*(double *)a > *(double *)b);
}

int smaller()
{
    int i;
    for(i = 1;i <= F;i ++)
    {
        if(tmp[0][i] < answer[0][i])    return 1;
    }
    for(i = 1;i <= R;i ++)
    {
        if(tmp[1][i] < answer[1][i])    return 1;
    }
    return 0;
}

void check()
{
    //calc ratio span, rough check
    double max,min;
    max = (double)tmp[0][F] / (double)tmp[1][1];
    min = (double)tmp[0][1] / (double)tmp[1][R];
    if(max < 3.0 * min)    return;
    //calc every ratio
    int i,j;
    int p = 0;
    for(i = 1;i <= F;i ++)
        for(j = 1;j <= R;j ++)
        {
            ratio[p ++] = (double)tmp[0][i] / (double)tmp[1][j];
        }
    qsort(ratio,p,sizeof(double),cmp);
    //calc the mean of ratio differences
    double sum = 0;
    double mean;
    for(i = 0;i < F * R - 1;i ++)
    {
        ratio_diff[i] = ratio[i + 1] - ratio[i];
        sum += ratio_diff[i];
    }
    mean = sum / (double)(F * R - 1);
    //calc variance * p;
    double variance = 0;
    for(i = 0;i < F * R - 1;i ++)
    {
        variance += pow((ratio_diff[i] - mean),2);
    }
    if(variance < minv)
    {
        minv = variance;
        memcpy(answer,tmp,sizeof(answer));
    }
    else if(variance == minv && smaller())
    {
        memcpy(answer,tmp,sizeof(answer));
    }
}

void dfs_rear(int n)  //try rear gears in ascending order
{
    int i;
    if(n > R)
    {
        check();
        return;
    }
    for(i = tmp[1][n - 1] + 1;i <= re - (R - n);i ++)
    {
        tmp[1][n] = i;
        dfs_rear(n + 1);
    }
}


void dfs_front(int n)   //try front gears in ascending order
{
    int i;
    if(n > F)
    {
        dfs_rear(1);
        return;
    }
    for(i = tmp[0][n - 1] + 1;i <= fe - (F - n);i ++)
    {
        tmp[0][n] = i;
        dfs_front(n + 1);
    }
}

int main()
{
    freopen("cowcycle.in","r",stdin);
    freopen("cowcycle.out","w",stdout);
    scanf("%d%d%d%d%d%d",&F,&R,&fb,&fe,&rb,&re);
    tmp[0][0] = fb - 1;
    tmp[1][0] = rb - 1;
    dfs_front(1);
    int i;
    for(i = 1;i < F;i ++)
        printf("%d ",answer[0][i]);
    printf("%d\n",answer[0][F]);
    for(i = 1;i < R;i ++)
        printf("%d ",answer[1][i]);
    printf("%d\n",answer[1][R]);
    fclose(stdout);
    return 0;
}

不过，上面代码的最长运行时间略微超过1s。如果可以更好的处理一下细节，程序的运行时间可以缩短一半，可以从一下几个角度优化：
1）浮点除法运算是相当慢的，尽量少用。
2）优化传动比排序算法（比如用链表+插入排序，据说会快一些）