USACO 4.2.4 Cowcycles 奶牛自行车 cowcycle
这是一道搜索题，题意不难理解，注释写得很清楚了。数据不是很BT，写个搜索，加些优化基本上就过了。似乎这道题同样算法用C++写比Pascal快得多。
搜索就是简单的搜索组合，用两个递归就可以了。
优化技巧：
- 最大传动比率至少是最小的3倍。这个其实不用算出比率在判断，只要不满足s1[F]/s2[1]-s1[1]/s2[R]>=3的都剪掉(s1表示前齿轮型号，s2表示后齿轮型号)。另外乘法计算要比除法快得多，上面判断式可以写成s1[F]*s2[R]>=3*s1[1]*s2[1]。这个剪枝很有效果。
- 改变求方差的方法，
。用右面的式子代替原来的。 - 当找到比当前更优秀的解的时候，不要用For循环一个一个复制当前解，用memcpy函数会更快。
- 最想不到地地方，排序方法！开始我写成快排，一直过不了。其实数据的数量太少的时候，用快排效率很低的。在这里最适合的是简单插入排序。这个剪枝的效率很惊人！
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;
}
上次修改时间 2017-02-03