USACO 4.2.4 Cowcycles 奶牛自行车 cowcycle

这是一道搜索题,题意不难理解,注释写得很清楚了。数据不是很BT,写个搜索,加些优化基本上就过了。似乎这道题同样算法用C++写比Pascal快得多。

搜索就是简单的搜索组合,用两个递归就可以了。

优化技巧:

  1. 最大传动比率至少是最小的3倍。这个其实不用算出比率在判断,只要不满足s1[F]/s2[1]-s1[1]/s2[R]>=3的都剪掉(s1表示前齿轮型号,s2表示后齿轮型号)。另外乘法计算要比除法快得多,上面判断式可以写成s1[F]s2[R]>=3s1[1]*s2[1]。这个剪枝很有效果。
  2. 改变求方差的方法,。用右面的式子代替原来的。
  3. 当找到比当前更优秀的解的时候,不要用For循环一个一个复制当前解,用memcpy函数会更快。
  4. 最想不到地地方,排序方法!开始我写成快排,一直过不了。其实数据的数量太少的时候,用快排效率很低的。在这里最适合的是简单插入排序。这个剪枝的效率很惊人!
USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: cowcycle LANG: C++

Compiling... Compile: OK

Executing... Test 1: TEST OK [0.011 secs, 1844 KB] Test 2: TEST OK [0.130 secs, 1848 KB] Test 3: TEST OK [0.108 secs, 1848 KB] Test 4: TEST OK [0.194 secs, 1848 KB] Test 5: TEST OK [0.421 secs, 1848 KB] Test 6: TEST OK [0.194 secs, 1844 KB] Test 7: TEST OK [0.443 secs, 1844 KB] Test 8: TEST OK [0.637 secs, 1844 KB]

All tests OK.

Your program ('cowcycle') produced all correct answers! This is your submission #2 for this problem. Congratulations!

/*
ID: cmykrgb1
PROG: cowcycle
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 11
using namespace std;
ifstream fi("cowcycle.in");
ofstream fo("cowcycle.out");

int s1[MAX],s2[MAX],ans1[MAX],ans2[MAX];
int F,R,F1,F2,R1,R2,cnt;
double rate[MAX*MAX],diff[MAX*MAX],minvf=0x7FFFFFFF;

void init()
{
    fi >> F >> R >> F1 >> F2 >> R1 >> R2;
    cnt=F*R;
}

void count()
{
    int i,j,k=0,l;
    double sum=0,avg,vf=0,sumf=0,p;
    for (i=1;i<=F;i++)
        for (j=1;j<=R;j++)
        {
            p=(double)s1[i]/s2[j];
            l=++k;
            while (rate[l-1]>=p)
            {
                rate[l]=rate[l-1];
                l--;
            }
            rate[l]=p;
        }
    for (i=1;i<=cnt-1;i++)
    {
        diff[i]=rate[i+1]-rate[i];
        sum+=diff[i];
        sumf+=diff[i]*diff[i];
    }
    avg=sum/(cnt-1);
    vf=sumf-sum*avg;
    if (vf<minvf)
    {
        minvf=vf;
        memcpy(ans1+1,s1+1,sizeof(int)*F);
        memcpy(ans2+1,s2+1,sizeof(int)*R);
    }
}

void sc2(int k,int w)
{
    int i;
    if (k==R+1)
    {
        if (s1[F]*s2[R]<3*s1[1]*s2[1])
            return;
        count();
        return;
    }
    for (i=w;i<=(R2-(R-k));i++)
    {
        s2[k]=i;
        sc2(k+1,i+1);
    }
}

void sc1(int k,int w)
{
    int i;
    if (k==F+1)
    {
        sc2(1,R1);
        return;
    }
    for (i=w;i<=(F2-(F-k));i++)
    {
        s1[k]=i;
        sc1(k+1,i+1);
    }
}

void print()
{
    int i;
    for(i=1;i<=F-1;i++)
        fo << ans1[i] << ' ';
    fo << ans1[F] << endl;
    for(i=1;i<=R-1;i++)
        fo << ans2[i] << ' ';
    fo << ans2[R] << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    sc1(1,F1);
    print();
    return 0;
}

相关日志