过桥问题-基础版

题目分析

• 人的个数确定了，他们往返最小次数也确定了
• 最快的两个人两个两个的往回带
• 从大的开始两个人组队
• 因为如果最后剩下一个人的话，肯定是剩下小那一个
• 倒着推理一下，肯定最后一次是最快的两个人一起过去

抛出代码

#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE 105

int num;
int list[SIZE];

int transport1(int num)//完全凭借最快的
{
	cout << "->" << list[0] << "," << list[num - 1] << endl;
	cout << "<-" << list[0] << endl;
	cout << "->" << list[0] << "," << list[num - 2] << endl;
	cout << "<-" << list[0] << endl;
	return list[num - 1] + list[0]+ list[num - 2] + list[0];

}

int transport2(int num)//借助第二快
{
	cout << "->" << list[0] << "," << list[ 1] << endl;
	cout << "<-" << list[0] << endl;
	cout << "->" << list[num - 1] << "," << list[num - 2] << endl;
	cout << "<-" << list[1] << endl;
	return list[ 1] + list[0] + list[num - 1] + list[1];

}

int  transport(int num)
{
	if (list[num - 2] + list[0] < 2 *list[1])
		return transport1(num);
	else
		return transport2(num);		
}



int main()
{
std::ios::sync_with_stdio(false);

int sum = 0;

cin >> num; 
//输入 num个数  


for (int i = 0; i < num; i++)
	cin >>list[i];
//每个人速度vi

sort(list,list+num);

while (num>3)
{
	sum+=transport(num);
	cout << "总时间：" << sum<< endl;
	num-=2;
}
if (num == 3)
{

	cout << "->" << list[0]<< "," << list[2] << endl;
	cout << "<-" << list[0]<< endl;
	cout << "->" << list[0]<< "," << list[1] << endl;
	sum += list[2];
	sum += list[0];
	sum += list[1];
}
else//2个
{
	cout << "->" << list[0]<< "," << list[1] << endl;
	sum += list[1];
}


cout << "总时间：" << sum << endl;


	return 0; 
}

课后作业

ZOJ 1877 POJ 2573