USACO Training Section 4.2 Cowcycles

英文原题 中文题译

 

大意：

 

这题题意比较绕口，读懂了题目，就差不多了。干脆把中文翻译的放上来吧。

 

秀·谢夫（小奶牛）在花花公子杂志上中了大奖，于是她从农村搬到了城郊的一座别墅中。可是她还常常怀念乡村的生活，总想回到原来的农村逛逛。为了环保，秀决定骑上为她量身定做的奶牛自行车（特殊的自行车，专门为牛蹄设计）。

秀大约有一吨重。同样的，秀在普通的奶牛自行车上，要想骑得平平稳稳，也不是一件容易的事。因此，调节奶牛自行车的变速器让秀心力交瘁。请帮助秀选择她的奶牛自行车前面 F （1 <= F <= 5）个齿轮和后面 R （1 <= R <= 10）个齿轮，使她的 F*R 奶牛自行车符合下面的标准：

 

1. 前面齿轮的型号（齿的数量）必须在给定的范围内。

2. 后面齿轮的型号（齿的数量）必须在给定的范围内。

3. 在每一种齿轮组合中，传动比率就是前面齿轮的齿数除以后面齿轮的齿数所得的商。

4. 最大的传动比率至少是最小的三倍。

5. 齿轮组合（已排好序）相邻两项的差的的方差应该达到最小。

 

分析和实现：

 

问题空间不算太大，直接暴搜，有几点需要注意的：

1. 最大传动比率不小于最小传动比率的三倍，作为剪枝条件，不过避免除法，用乘法得到

2. 遍历前后齿轮可以用一个递归，不过用两个更直观些。

3. 比率的计算可以在递归过程中完成，可避免大量重复运算。

4. 给传动比排序时若用lib的qsort或STL的sort效率很低（因为元素太少），简单的直接写个比较排序比用库函数快两倍。

5. 传动比方差的计算时可避免一些浮点运算。

注意一下变量、函数命名，清晰化，一次可过。

 

/*
ID: blackco3
TASK: cowcycle
LANG: C++
*/
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
const int _max_front_(5), _max_rear_(10), _max_pair_(_max_front_*_max_rear_) ;
 
int front[_max_front_], rear[_max_rear_] ;
int best_front[_max_front_], best_rear[_max_rear_];
int n_front, n_rear, min_front, max_front, min_rear, max_rear, n_pair;
double rate[_max_pair_], *p_rate=rate, rate_sort[_max_pair_], diff, min_diff=(double)0x7fffffff ;
 
void set_rears( int no, int min_val )
{
	if( no==n_rear ) {
		if( front[n_front-1]*rear[n_rear-1]<3*front[0]*rear[0] )
			return;
		memcpy( rate_sort, rate, sizeof(double)*n_pair ) ;
		sort( rate_sort, rate_sort+n_pair ) ;
		diff=0 ;
		for(double *pr=rate_sort; pr!=rate_sort+n_pair-1; pr++) 
			diff += (*pr - *(pr+1))*(*pr - *(pr+1)) ;
		diff -= (rate_sort[n_pair-1]-rate_sort[0])*((rate_sort[n_pair-1]-rate_sort[0])/(n_pair-1));
		if ( diff < min_diff) {
			min_diff = diff;
			memcpy(best_front, front, sizeof(int)*n_front );
			memcpy(best_rear, rear, sizeof(int)*n_rear );
		}
		return ;
	}
	for( int i=min_val; i<=(max_rear-(n_rear-no-1)); i++) {
		rear[no]=i;
		for( int i_front=0; i_front<n_front; i_front++ )
			*(p_rate++) = ((double)front[i_front])/i ;
		set_rears( no+1, i+1 );
		p_rate -= n_front ;
	}
}
 
void set_fronts( int no, int min_val) {
	if ( no==n_front )
		set_rears( 0, min_rear ) ;
	else
		for( int i=min_val; i<=(max_front-(n_front-no-1)); i++)
			set_fronts( no+1, (front[no] = i) + 1 );
}
 
int main(){
	freopen("cowcycle.in", "r", stdin);
	freopen("cowcycle.out", "w", stdout);
	cin >> n_front >> n_rear >> min_front >> max_front >> min_rear >> max_rear ;
	n_pair = n_front * n_rear ;

	set_fronts( 0, min_front ) ;
	
	for(int i=0; i<n_front; i++ )
		cout << best_front[i] << (i!=n_front-1 ? ' ' : '\n');
	for(int i=0; i<n_rear; i++ )
		cout << best_rear[i] << (i!=n_rear-1 ? ' ' : '\n');
    return 0;
}