博文
UVa 102 解题小结——多亏n只是3，要不就跪了
|||
这道题假设有Brown，Green，Clear三种颜色的杯子，现在有三个盒子，每个盒子中有三种数量不等的杯子。现在要使每个箱子中只有一种颜色的杯子，求需要移动最小的杯子数目以及之后每个箱中杯子的组成。
这道题应该有更好的算法，但是，以本人的数学修为，想不到…………幸亏只有3种，所以使用穷举法可以在较短时间内进行计算。但其算法复杂度为$O(n!)$,当n变化时，该方法的时间会变得很长，以致不可计算。
源码：# include <iostream>
using namespace std;
int min(int* n,int num,int &no)
{
int r=n[0];
no=0;
for(int i=1;i<num;++i)
{
if(r>n[i])
{
r=n[i];
no=i;
}
}
return r;
}
int main()
{
int num[9],res[6];
while(cin>>num[0])
{
for(int i=1; i<9;++i)//输入
{
cin>>num[i];
}
//GCB 023478
//GBC 024567
//CGB 013578
//CBG 014568
//BGC 123567
//BCG 123468
res[5]=num[0]+num[2]+num[3]+num[4]+num[7]+num[8];
res[4]=num[0]+num[2]+num[4]+num[5]+num[6]+num[7];
res[3]=num[0]+num[1]+num[3]+num[5]+num[7]+num[8];
res[2]=num[0]+num[1]+num[4]+num[5]+num[6]+num[8];
res[1]=num[1]+num[2]+num[3]+num[5]+num[6]+num[7];
res[0]=num[1]+num[2]+num[3]+num[4]+num[6]+num[8];
int no(0),result(0);
result=min(res,6,no);
if(no==0)cout<<"BCG "<<result<<endl;
else if(no==1)cout<<"BGC "<<result<<endl;
else if(no==2)cout<<"CBG "<<result<<endl;
else if(no==3)cout<<"CGB "<<result<<endl;
else if(no==4)cout<<"GBC "<<result<<endl;
else if(no==5)cout<<"GCB "<<result<<endl;
}
}
https://wap.sciencenet.cn/blog-723765-645397.html
上一篇：UVa 101 解题小结——要认真读题！切记！切记！
下一篇：UVa 103 解题小结——感觉解出来了，但是脑袋好乱
