Beyond the Void
BYVoid
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]>=3*s1[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;
}

上次修改时间 2017-02-03

相关日志