UVA 102: Ecological Bin Packing

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38

题目大意:

     装箱问题也是背包问题是一个非常容易理解题意但是非常难的问题,是NP问题。但是本题是一个简单的垃圾分类问题。每个垃圾桶里面都有3个分别是棕色、绿色、白色的分类箱子,每个垃圾桶里面的每个箱子里面都有垃圾,现在要使每个垃圾桶里面只有一个颜色的箱子有垃圾,其它箱子里面的垃圾要移动到别个垃圾桶里面,要使移动的垃圾最少。

解题思路:

      枚举法,每个垃圾桶可以装的颜色都遍历一遍,求出移动最小的那个值就是答案,还要比较方案字符串,最小值相同输出字符串字典序小的。

解题代码:

#include<iostream>
#include<string>
using namespace std;
int a[9];
string s("BGC");
void work(){
	string s1=("BGC");
	int min=1<<31-1;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int z=0;z<3;z++)
				if(i!=j&&j!=z&&i!=z){
					string s2;
					s2+=s[i];
					s2+=s[j];
					s2+=s[z];
					int tmp=0;
				    for(int k=0;k<9;k++)
						if(i!=k&&k!=3+j&&k!=6+z)
							tmp+=a[k];
					if(min>tmp) min=tmp,s1=s2;
					else
						if(min==tmp){
							if(s1>s2) s1=s2;
						}
				}
	cout<<s1<<' '<<min<<endl;
}
int main(){
	while(cin>>a[0]){
		for(int i=1;i<9;i++)
				cin>>a[i];
		work();
	}
	return 0;
}

扩展知识:http://baike.baidu.com/view/841810.htm

UVA 100: The 3n + 1 problem

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

题目大意:

      3n+1问题是一个非常经典的数学问题,目前还没有人能够证明。一个数通过3N+1的算法会等到一个序列,序列肯定会以1结尾,例如22的序列是22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1,它的序列长度是16.

     现在要给你一个范围,n,m,让你求出这个范围你每个数的3N+1序列最长是多少。

解题思路:

      这个问题是UVA中最简单的题目,打算按那个UVA的难度排行表一题一题做下去。

      解决办法是将这个范围内的数,每个都求出它的序列长度,然后保留最大的长度。

      这题有一个trick,就是给你n,m并不是一定是n<=m,因为这个做错一次,所以做题时候要细心注意细节条件。一些没有提到的条件要想到。

解题代码:

#include<iostream>
using namespace std;
int t3n1(int n){
	int num=1;
	while(n!=1){
		if(n%2)
			n=3*n+1;
		else
			n=n/2;
		num++;
	}
	return num;
}
int work(int n,int m){
	int max=0,tmp;
	for(int i=n;i<=m;i++)
		if(max<(tmp=t3n1(i)))
			max=tmp;
	}
	return max;
}
int main(){
	int n,m;
	while(cin>>n>>m){
		if(n>m){
			cout<<n<<' '<<m<<' '<<work(m,n)<<endl;
		}
		else
			cout<<n<<' '<<m<<' '<<work(n,m)<<endl;
	}
	return 0;
}

扩展知识:http://www.equn.com/3x+1/

 

 

UVA难度排名

阅读全文