黑书上面的第一个问题，写了很久，又参考了网上的代码。算法的思想是枚举。 首先截图题目如下：
oj上面的题目在http://acm.fzu.edu.cn/problem.php?pid=1515 粘贴代码如下， #include #include #include #include using namespace std; double x[2],y[2],z[2]; const double PI=acos(-1.0);//PI的表示//定义结构体，代表盒子里气球的坐标struct point{ double x,y,z; };//判断气球距盒子的最短距离 double side(point p) { double minx=min(fabs(p.x-x[0]),fabs(p.x-x[1])); double miny=min(fabs(p.y-y[0]),fabs(p.y-y[1])); double minz=min(fabs(p.z-z[0]),fabs(p.z-z[1])); return min(minx,min(miny,minz)); }//距离公式 double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)); } int main() { fstream cin("input_1.txt"); int n; point a[6]; int b[6]={0,1,2,3,4,5}; double v,r[6],mind,s,ans; while(cin>>n) { ans=0; for(int i=0;i<2;i++) { cin>>x[i]>>y[i]>>z[i]; } for(int i=0;i>a[i].x>>a[i].y>>a[i].z; } do { v = 0; memset (r,0,sizeof(r)); for(int i=0;i s) mind = s; } r[b[i]] = mind; v+=4/3.0*PI*mind*mind*mind; } if (v > ans) ans = v; } while(next_permutation(b,n+b));//依次枚举各种情况进行判断，选择最优解 printf("%.0lf ",fabs((x[1]-x[0])*(y[1]-y[0])*(z[1]-z[0]))-ans); } system("pause"); return 0; }
上面代码的时间复杂度为O(n^3)，有待优化，在网上看到用DFS的效率提高不少，过一阵做搜索问题时再研究一下。 下面提高几组数据，供测试使用，都是网上找的。 INPUT： 2 0 0 0 10 10 10 3 3 3 7 7 7 4 73 256 -38 -175 944 136 -37 332 1 -63 743 64 48 472 -32 35 753 38 6 808 877 -957 661 329 -738 763 572 -792 687 539 -879 673 795 -811 679 500 -783 717 545 -883 667 629 -825OUTPUT： 774 27763968 16491870