学步园

吼吼，趁机秀一秀我的小捷

INPUT FORMAT:

(file cowcycle.in)

第一行是 F 和 R，表示前齿轮和后齿轮的数量。

第二行包括 4 个数字：F1，F2（25 <= F1 < F2 <= 80），R1，R2（5 <= R1 < R2 <= 40）。从 F1 到 F2 型号的前齿轮都是可用的；从 R1 到 R2 型号的后齿轮都是可用的。至少会有一组合法的解。

题目要求：

找出符合下面的标准：

1. 前面齿轮的型号（齿的数量）必须在给定的范围内。
2. 后面齿轮的型号（齿的数量）必须在给定的范围内。
3. 在每一种齿轮组合中，传动比率就是前面齿轮的齿数除以后面齿轮的齿数所得的商。
4. 最大的传动比率至少是最小的三倍。
5. 齿轮组合的转动比率（已排好序）相邻两项的差的的方差（见下面的例子） 应该达到最小。

计算并确定最佳齿轮组合（其中 F 个前齿轮，R 个后齿轮），使方差最小（传动比率至少是 3x）。

题解：直接搜索所有可能的组合找出符合和条件并方差最小那个组合，我开始一直不敢写觉得直接爆搜会超时，但实在没有想到别的什么办法了只好硬着头皮爆搜，没想到异常顺利的一A了。这道题给的数据不是很强，所以放心爆搜吧。

下面是代码：

#include<cstdio>
#include<algorithm>

using namespace std;

FILE *in,*out;
int total,f,r,fs,fe,rs,re,farr[50],rarr[50],ansf[50],ansr[50];
double ratio[1000],var;

void combf(int s,int e,int index);
void combr(int s,int e,int index);
void check(void);

int main()
{
    in=fopen("cowcycle.in","r");
    out=fopen("cowcycle.out","w");
    
    fscanf(in,"%d%d",&f,&r);
    fscanf(in,"%d%d%d%d",&fs,&fe,&rs,&re);
    total=f*r;
    var=100000000;
    combf(fs,fe,0);
    
    for(int i=0;i<f-1;i++) fprintf(out,"%d ",ansf[i]);
    fprintf(out,"%d\n",ansf[f-1]);
    for(int i=0;i<r-1;i++) fprintf(out,"%d ",ansr[i]);
    fprintf(out,"%d\n",ansr[r-1]);
    
    fclose(in);
    fclose(out);
    return 0;
}

void combf(int s,int e,int index)
{
     if(index==f)
     {
           combr(rs,re,0);
           return ;
     }
     if(s>e) return ;
     for(int i=s;i<=e;i++)
     {
         farr[index]=i;
         combf(i+1,e,index+1);
     }
}

void combr(int s,int e,int index)
{
     if(index==r)
     {
          int fmax=farr[f-1];
          int fmin=farr[0];
          int rmax=rarr[r-1];
          int rmin=rarr[0];
          if((fmax*rmax)/(rmin*fmin)<3) return ;//唯一的一个剪枝
          check();
          return ;
     }
     if(s>e) return ;
     for(int i=s;i<=e;i++)
     {
         rarr[index]=i;
         combr(i+1,e,index+1);
     }
}

void check(void)
{
     for(int i=0;i<f;i++)
     {
          for(int j=0;j<r;j++) ratio[i*r+j]=(double)farr[i]/rarr[j];
     }
     sort(ratio,ratio+total);
     for(int i=0;i<total-1;i++) ratio[i]=ratio[i+1]-ratio[i];
     double mean=0;
     for(int i=0;i<total-1;i++) mean+=ratio[i];
     mean/=(total-1);
     double tv=0;
     for(int i=0;i<total-1;i++)
     {
           double diff = ratio[i]-mean;
           tv+=diff*diff;
     }
     tv/=(total-1);
     if(tv<var)
     {
           var=tv;
           for(int i=0;i<f;i++) ansf[i]=farr[i];
           for(int i=0;i<r;i++) ansr[i]=rarr[i];
     }
}