【USACO4.2.4】奶牛自行车

83 阅读 0 评论 55 点赞

我是靠谱客的博主踏实红酒，最近开发中收集的这篇文章主要介绍【USACO4.2.4】奶牛自行车，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

其实是个水题，就按照题目意思来。

但是我题目意思看错了3次…… 写了3个多小时……

Executing...
   Test 1: TEST OK [0.008 secs, 3396 KB]
   Test 2: TEST OK [0.095 secs, 3396 KB]
   Test 3: TEST OK [0.054 secs, 3396 KB]
   Test 4: TEST OK [0.127 secs, 3396 KB]
   Test 5: TEST OK [0.267 secs, 3396 KB]
   Test 6: TEST OK [0.165 secs, 3396 KB]
   Test 7: TEST OK [0.292 secs, 3396 KB]
   Test 8: TEST OK [0.475 secs, 3396 KB]

All tests OK.

	for (back_min = r1; back_min + R - 1 <= r2; ++ back_min)// 穷举后轮最小值back_min
	{
		for (back_max = back_min + R - 1; back_max <= r2; ++ back_max) //后轮最大值back_max
		{
			for (front_min = f1; front_min + F - 1 <= f2; ++ front_min) //前轮最小值，
			{
				for (front_max = front_min + F - 1; front_max <= f2; ++ front_max) //前轮最大值
				{
					if (front_min * back_min * 3 > front_max * back_max)	continue; //直接不符合要求，退出
					usd1[1] = front_min;
					usd2[1] = back_min;
					usd2[R] = back_max;
					usd1[F] = front_max;
					if (F == 1) dfs_front(front_min, 0);
					else dfs_front(front_min, 1);
				}
			}
		}
	}

强行穷举前后轮最大值最小值范围，然后根据题目的条件的，大小轮子比率3倍，来直接剪掉一些范围，然后在范围内进行枚举，求解

我是用2个DFS强行穷举出所有情况，然后计算方差。

先看成是选择轮子的方差了……然后又看成是轮子比率的方差，

结果求的是—— 轮子比率排序后的差的方差……

/*
TASK:cowcycle
LANG:C++
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
//F,R为1的情况暂时没有考虑

int F, R;
int f1, f2, r1, r2;

void init()
{
	cin >> F >> R;
	cin >> f1 >> f2;
	cin >> r1 >> r2;
}

int back_min, back_max, front_min, front_max;
//int ans
int usd1[100], usd2[100], tot1;
int output_usd1[100], output_usd2[100];
double ans=10000000000;

double p[1000],pp[1000];
int tp, tt;
inline void check()
{
	tp = tt = 0;
	for (int i = 1; i <= F; ++ i)
		for (int j = 1; j <= R; ++ j)
			pp[++tp] = (double)usd1[i] / (double)usd2[j]	;
	sort(pp + 1, pp + 1 + tp);
	for (int i = 1; i < tp; ++ i)	p[i] = pp[i + 1] - pp[i];
	--tp;
	double ave,tot(0), tmp(0);
	for (int i = 1; i <= tp; ++ i)	tot += p[i];
	ave = tot / tp;
	for (int i = 1; i <= tp; ++ i)	tmp += (p[i] - ave) * (p[i] - ave);
	tmp /= tp;
	if (tmp == ans)
	{
		for (int i = 1; i <= F; ++ i)
		{
			if (usd1[i] < output_usd1[i])	goto ok1;	
			if (usd1[i] > output_usd1[i])	return;
		}
		for (int i = 1; i <= R; ++ i)
		{
			if (usd2[i] < output_usd2[i])	goto ok1;	
			if (usd2[i] > output_usd2[i])	return;
		}
	
	}
	if (tmp < ans)
	{
		ans = tmp;
		ok1:;
		memmove(output_usd1 + 1, usd1 + 1, sizeof(int) * F);
		memmove(output_usd2 + 1, usd2 + 1, sizeof(int) * R);
	}
}

void dfs_back(int k,int tot)
{
	if (back_max - k + 1 < R - tot)	return;
	if (tot == R - 1)
	{
		check();	
		return;
	}
	usd2[tot + 1] = k;
	dfs_back(k + 1, tot + 1);
	dfs_back(k + 1, tot);
}

void dfs_front(int k, int tot)
{
	if (front_max - k + 1 < F - tot)	return; //不够填充的，return
	if (tot == F - 1) //最后一格直接填进去
	{
		dfs_back(back_min + 1, 1);
		return ;
	}
	usd1[tot + 1] = k;//第tot个数字选择k
	dfs_front(k + 1, tot + 1);
	dfs_front(k + 1, tot);
}

void doit()
{
	for (back_min = r1; back_min + R - 1 <= r2; ++ back_min)// 穷举后轮最小值back_min
	{
		for (back_max = back_min + R - 1; back_max <= r2; ++ back_max) //后轮最大值back_max
		{
			for (front_min = f1; front_min + F - 1 <= f2; ++ front_min) //前轮最小值，
			{
				for (front_max = front_min + F - 1; front_max <= f2; ++ front_max) //前轮最大值
				{
					if (front_min * back_min * 3 > front_max * back_max)	continue; //直接不符合要求，退出
					usd1[1] = front_min;
					usd2[1] = back_min;
					usd2[R] = back_max;
					usd1[F] = front_max;
					if (F == 1) dfs_front(front_min, 0);
					else dfs_front(front_min, 1);
				}
			}
		}
	}
	
	for (int i = 1; i < F; ++ i)	cout<<output_usd1[i]<<" ";
	cout<<output_usd1[F]<<endl;
	for (int i = 1; i < R; ++ i)	cout<<output_usd2[i]<<" ";
	cout<<output_usd2[R]<<endl;

}

int main()
{
	freopen("cowcycle.in", "r",stdin);
	freopen("cowcycle.out","w",stdout);
	init();
	doit();
	return 0;
}