usaco training 4.2.4 Cowcycles 题解 - c++编程基础

Cowcycles题解
Originally by Don Gillies

[International readers should note that some words are puns on cows.]

Having made a fortune on Playbov magazine, Hugh Heifer has moved from his original field in the country to a fashionable yard in the suburbs. To visit fond pastoral memories, he wishes to cowmmute back to his old stomping grounds. Being environmentally minded, Hugh wishes to transport himself using his own power on a Cowcycle (a bicycle specially fitted for his neatly manicured hooves).

Hugh weighs over a ton; as such, getting smoothly up to speed on traditional cowcycle gear sets is a bit challenging. Changing among some of the widely spaced gear ratios causes exertion that's hard on Hugh's heart.

Help Hugh outfit his Cowcycle by choosing F (1 <= F <= 5) gears (sprockets) in the front and R (1 <= R <= 10) gears in the rear of his F*R speed cowcycle subject to these rules:

Calculate the mean and variance of a set of differences (x_i in this formula) by the following formulae:


<  http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcHJlPgo8cD5EZWR1Y2UgYW5kIHByaW50IHRoZSBvcHRpbWFsIHNldHMgb2YgRiBmcm9udCBnZWFycyBhbmQgUiByZWFyIGdlYXJzIHNvIHRoYXQgdGhlIHZhcmlhbmNlIGlzIG1pbmltaXplZCAoYW5kIHRoZSByYXRpb3Mgc3BhbiBhIGZhY3RvciBvZiBhdCBsZWFzdCAzeCkuPC9wPgo8aDM+UFJPR1JBTSBOQU1FOiBjb3djeWNsZTwvaDM+CjxoMz5JTlBVVCBGT1JNQVQ8L2gzPgo8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBGIGFuZCBSLCB0aGUgbnVtYmVycyBvZiBmcm9udCBhbmQgcmVhciBnZWFycy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGZvdXIgbnVtYmVyczogRjEsIEYyICgyNSA8PSBGMSA8IEYyIDw9IDgwKSwgUjEsIGFuZCBSMiAoNSA8PSBSMSA8IFIyIDw9IDQwKS4gQWxsIGZyb250IGdlYXJzIGZyb20gRjEgdGhyb3VnaCBGMiBhcmUKIGF2YWlsYWJsZTsgYWxsIHJlYXIgZ2VhcnMgZnJvbSBSMSB0aHJvdWdoIFIyIGFyZSBhdmFpbGFibGUuIFRoZXJlIHdpbGwgZXhpc3QgYXQgbGVhc3Qgb25lIGxlZ2FsIHNldCBvZiBnZWFycy48L3A+CjxoMz5TQU1QTEUgSU5QVVQgKGZpbGUgY293Y3ljbGUuaW4pPC9oMz4KPHByZSBjbGFzcz0="brush:java;">2 5
39 62 12 28

OUTPUT FORMAT

Display the number of teeth on the set of F chosen front gears, from smallest to largest, on the first line of output (separated by spaces). Display the number of teeth on the set of R chosen rear gears, from smallest to largest, on the second line of output. All gears have an integer number of teeth, of course.

If multiple optimal answers exist, output the answer with the smallest front gear set (smallest first gear, or smallest second gear if first gears match, etc.). Likewise, if all first gears match, output the answer with the smallest rear gear set (similar rules to the front gear set).

SAMPLE OUTPUT (file cowcycle.out)

39 53
12 13 15 23 27

Comment

The challenge in this problem is "reading the problem". Don't read further if you are working on that level of challenge. If the problem is just completely unclear to you, read in.

The problem wants you to find "an optimal set of gear ratios" such that the spacing between the ratios is most uniform. Consider the test case above:

2 5
39 62 12 28

For each of these possibilities, calculations like the following. This example considers in some sense the "first" case: front gears of 39 and 40, rear gears of 12, 13, 14, 15, and 16.

First, calculate all the possible ratios:

39/12 = 3.25000000000000000000
39/13 = 3.00000000000000000000
39/14 = 2.78571428571428571428
39/15 = 2.60000000000000000000
39/16 = 2.43750000000000000000
40/12 = 3.33333333333333333333
40/13 = 3.07692307692307692307
40/14 = 2.85714285714285714285
40/15 = 2.66666666666666666666
40/16 = 2.50000000000000000000

Then, sort them:

39/16 = 2.43750000000000000000
40/16 = 2.50000000000000000000
39/15 = 2.60000000000000000000
40/15 = 2.66666666666666666666
39/14 = 2.78571428571428571428
40/14 = 2.85714285714285714285
39/13 = 3.00000000000000000000
40/13 = 3.07692307692307692307
39/12 = 3.25000000000000000000
40/12 = 3.33333333333333333333

Then, calculate the absolute value of the differences:

2.43750000000000000000 - 2.50000000000000000000 = 0.06250000000000000000
2.50000000000000000000 - 2.60000000000000000000 = 0.10000000000000000000
2.60000000000000000000 - 2.66666666666666666666 = 0.06666666666666666666
2.66666666666666666666 - 2.78571428571428571428 = 0.11904761904761904762
2.78571428571428571428 - 2.85714285714285714285 = 0.07142857142857142857
2.85714285714285714285 - 3.00000000000000000000 = 0.14285714285714285715
3.00000000000000000000 - 3.07692307692307692307 = 0.07692307692307692307
3.07692307692307692307 - 3.25000000000000000000 = 0.17307692307692307693
3.25000000000000000000 - 3.33333333333333333333 = 0.08333333333333333333

Then, calculate the mean and variance of the set of numbers on the right, above. The mean is (I think): 0.0995370370370370370366666. The variance is approximately 0.00129798488416722.

Of course this set of gears is not valid, since it does not have a 3x span from highest gear to lowest.

Find the set of gears that minimizes the variance and has a 3x or greater span.

这道题乍一看把我吓了一跳。根据极限数据：C(56，5)*C(36，10)=9.7*10^14。不算排序就已经严重超时了！但是我还是抱着做做看的思路，直接深搜枚举所有情况并记录。由于我对常数的管理，使搜索的效率大大提高。

剪枝和优化：①如果小于三倍就可以直接退出，没必要算下去了。公式原来是:a[f]/b[1]<3*a[1]/b[f]，但是由于乘法比除法快很多，我们可以化成a[f]*b[f]<3*a[1]*b[1]。

②求方差时，因为排过序，不必像解释的那样取绝对值，而是大的减小的。

③省掉不必要的函数。我果断把搜完后判断的处理和后齿轮的枚举放在了一起（inline的别说）

④在枚举齿轮的时候，没有用那种flag数组的记录，而是直接加一个参数直接循环。

。代码：

/*
PROG:cowcycle
ID:juan1973
LANG:C++
*/
#include
   
    
using namespace std;
int a[57],b[37],ansa[57],ansb[37],f,r,f1,r1,f2,r2,i,cnt;
double sum,tot,ans,c[2017],t;
void find_r(int k,int step)
{
  int i,j;
  if (step==r+1)
  {
    if (a[f]*b[r]<3*a[1]*b[1]) return;   //if (a[f]/b[1]<3*a[1]/b[r])
    cnt=0;
    sum=tot=0;
    for (i=1;i<=f;i++)
      for (j=1;j<=r;j++)
        c[++cnt]=double(a[i])/double(b[j]);
    for (i=1;i
    
     c[j]) {t=c[i];c[i]=c[j];c[j]=t;} for (i=1;i