程序员人生网站导航

UVa 10012 有多大没AC，待修改

栏目：综合技术时间：2015-03-23 08:39:48

题意：给出1些圆的半径，把所有圆放到1个矩形里，要求所有圆都必须与矩形的最下边相切，求矩形的最小长度。

本来写得很快，以为是1道水题，结果有太多情况没斟酌。。我是依照最左圆的半径加上每两相切圆的圆心间水平距离再加上最右圆的半径写的，有太多情况没斟酌。1会补上1个，缝缝补补的，现在都有些晕了，现在还遗漏的情况是，我只斟酌了第2个圆比第1个圆能到更左，和倒数第2个圆比倒数第1个圆能到更右，但是第3个圆或第4个圆也可能比它左侧的圆更能到达左侧的，右侧类似。。这就像，只补上了i⑵号圆与i号圆相切，而没有斟酌i号圆可能和i⑶号圆也能够相切。。。

参考此处和此处，给出了各种情况。

我觉得不会再修改这个思路了。。最多重新写1个。。。

下面是1些测试数据：

input

101

3 2.0 0.4 2.0
8 1.344 0.852 0.269 1.472 3.170 1.329 0.579 2.847
3 0.196 0.009 0.735
7 0.030 3.821 1.368 1.545 5.434 0.934 0.105
3 0.467 0.889 0.461
7 0.744 1.173 1.035 0.354 0.300 1.102 0.708
6 1.419 5.220 1.208 0.714 1.741 8.151
7 0.453 2.879 1.834 3.639 1.361 0.558 1.280
8 10.519 0.553 4.513 0.911 1.170 0.293 0.678 1.463
2 1.069 0.616
5 1.780 3.458 2.220 0.659 0.750
8 0.146 1.085 7.379 0.992 4.334 3.427 0.608 2.375
1 0.155
5 0.119 2.052 0.379 2.150 0.693
4 63.499 0.249 3.666 0.322
5 1.890 4.796 0.583 0.187 0.347
1 1.079
4 0.209 1.862 1.430 5.867
8 3.265 0.590 0.054 1.583 0.074 1.585 0.525 0.989
4 2.232 7.205 150.375 1.467
1 11.740
6 10.779 3.807 1.716 0.428 0.536 1.224
4 1.071 2.685 0.794 0.117
4 0.608 0.486 0.135 4.533
1 0.469
8 2.294 0.756 10.556 3.538 2.250 0.383 0.858 1.160
3 2.463 1.446 1.809
5 2.174 0.154 0.322 0.539 0.847
7 0.429 1.694 2.170 0.214 0.369 0.275 8.182
5 2.159 0.739 1.132 0.733 0.328
3 7.906 3.212 1.724
1 3.759
4 2.750 1.045 1.434 19.391
2 0.241 12.710
4 0.900 0.978 0.568 0.968
7 1.056 0.084 1.089 3.910 0.114 1.221 2.411
3 2.301 1.375 0.298
2 0.376 0.532
4 2.275 0.261 0.087 2.705
5 0.605 1.057 0.257 0.706 0.861
3 0.203 0.627 0.848
1 4.048
5 3.357 0.641 4.038 0.864 0.667
8 0.252 0.416 1.932 0.365 0.621 0.502 8.299 0.318
2 40.436 3.087
7 0.682 2.496 0.322 0.786 0.128 0.625 0.438
4 1.042 2.291 0.724 1.504
8 1.460 5.581 0.001 25.125 1.713 2.704 0.342 0.716
6 0.102 0.469 0.859 4.451 2.170 1.602
8 1.830 14.377 0.517 0.685 1.184 0.001 1.011 1.385
6 0.855 0.000 1.823 0.768 0.426 1.157
5 0.647 2.051 0.537 1.676 0.339
3 3.623 0.364 0.994
8 0.947 1.024 0.263 0.773 1.279 4.074 49.961 0.065
2 6.345 16.925
5 4.651 0.156 1.075 0.480 2.629
5 1.256 0.227 0.054 0.035 1.912
2 1.203 0.751
7 5.175 0.518 1.108 8.091 0.274 1.003 0.555
6 0.291 0.175 0.370 7.216 0.554 1.628
7 0.847 0.676 0.577 0.492 1.407 0.868 10.257
2 0.812 1.108
6 1.286 19.802 0.499 0.333 0.598 13.306
3 0.688 0.263 21.964
1 0.748
8 0.203 1.499 23.346 1.314 2.114 0.833 1.757 14.082
7 7.280 0.942 0.389 1.521 1.467 0.963 2.634
6 0.588 0.239 0.647 2.450 1.536 0.291
8 22.087 1.160 10.010 0.527 1.168 0.720 0.184 0.670
7 3.225 1.402 1.486 2.549 1.023 1.008 2.263
2 0.955 1.202
5 3.073 7.774 6.587 8.906 1.282
6 0.301 0.835 4.213 0.848 5.414 1.315
4 0.731 2.590 2.308 0.235
1 1.250
8 0.383 3.919 0.738 0.429 0.663 0.698 1.331 1.531
7 1.280 0.356 0.686 1.039 0.680 0.058 0.490
6 1.031 0.174 1.945 0.773 0.680 0.466
8 0.413 0.689 4.510 0.694 1.453 3.161 0.971 0.283
3 0.781 1.030 1.666
3 0.061 1.953 1.654
3 0.036 0.741 0.477
3 1.826 2.268 2.851
7 0.319 2.537 1.363 35.278 0.172 6.054 4.533
2 5.517 1.447
2 0.226 0.493
8 2.559 0.443 4.470 1.445 1.162 0.258 0.193 1.644
4 0.563 3.274 1.186 0.803
8 0.303 7.870 17.105 0.734 1.000 6.424 3.592 2.105
7 1.028 2.475 1.486 0.505 0.480 0.133 1.702
2 0.528 1.190
4 8.753 0.326 0.944 0.843
2 0.870 1.001
4 0.324 0.899 0.772 5.190
8 0.182 2.026 12.486 2.303 1.066 4.099 0.923 1.286
7 2.644 0.931 0.367 0.779 0.618 0.190 11.166
8 1.903 0.002 1.174 3.766 0.789 1.874 7.221 0.830
8 0.579 0.657 0.518 0.567 19.806 0.080 0.186 2.428
6 0.778 3.006 5.973 8.024 0.042 0.268
7 0.148 0.226 3.190 0.146 1.708 0.398 0.317
5 2.595 0.559 0.306 1.292 1.908

output

8.000, not 7.578

20.334 1.690 21.870 3.497 9.809 28.015 20.397 28.812 3.308 14.987 32.716 0.310 9.063 126.998 12.707 2.158 15.695 14.333 300.750 23.480 27.398 8.177 9.066 0.938 31.701 11.251 6.269 19.737 8.877 22.398 7.518 38.782 25.420 6.718 17.124 7.233 1.802 9.941 6.453 3.018 8.096 14.976 18.239 80.872 8.694 10.299 54.389 15.754 28.754 9.145 8.777 8.412 99.922 43.996 15.114 6.267 3.855 26.208 15.699 20.514 3.817 65.572 43.928 1.496 73.691 23.309 9.041 61.835 23.824 4.300 49.918 20.044 10.248 2.500 15.232 8.357 8.829 18.325 6.712 7.202 2.407 13.743 70.560 12.615 1.387 20.281 9.581 61.570 13.133 3.303 17.506 3.737 10.409 34.572 24.677 27.367 39.612 32.294 9.566 11.336

Code：

//没AC，有问题的。。 #include<stdio.h> #include<string.h> #include<math.h> void dfs(int cur,int m,double len); double a[10]; int vis[10]; int A[10]; double yy[10]; double bestlen; int main() { int n; scanf("%d",&n); while(n-->0) { memset(vis,0,sizeof(vis)); int m; int num=0; scanf("%d",&m); for(int i=0;i<m;++i) { scanf("%lf",&a[i]); if(a[i]==0) { vis[i]=1; num++;} } bestlen=10000000000.0; dfs(0,m-num,0); printf("%.3lf ",bestlen); } return 0; } void dfs(int cur,int m,double len) { if(len>=bestlen) return ; if(cur==m) { if(yy[m⑴]+a[A[m⑴]]<a[A[m⑵]]) len=len-yy[m⑴]-a[A[m⑴]]+a[A[m⑵]]; bestlen=len<bestlen?len:bestlen; } else for(int i=0;i<m;++i) { if(!vis[i]) { vis[i]=1; A[cur]=i; double len2=len;//复制len，这样在dfs下面的代码就不需要恢复len了。 double dd=0; if(cur==0) len2=len2+a[i];//第1个位置，只需要加第1个的半径 else { double dxie=a[i]+a[A[cur⑴]]; double dy=a[i]-a[A[cur⑴]]; dd=sqrt(dxie*dxie-dy*dy); len2=len2+dd; yy[cur]=dd; } if(cur==m⑴) len2=len2+a[i];//最后1个位置，还应再加1个最后的半价 if(cur==1) { if(a[A[0]]+dd<a[A[1]]) len2=len2-a[A[0]]-dd+a[A[1]]; yy[1]=a[A[1]];} if(cur<2) dfs(cur+1,m,len2); double lyy=0;//当前圆与之前的圆，用半径和的平方减去半径差的平方的值 int j=0; for(;j<cur⑴;++j)//枚举当前圆与第0、1...圆 { double dxie=a[i]+a[A[j]]; double dy=a[i]-a[A[j]; lyy=sqrt(dxie*dxie-dy*dy); double changdd=0;//当前圆与第j圆的水平距离 for(int k=j+1;k<=cur;++k) changdd+=yy[k]; if(changdd<lyy) { len2=len2-changdd+lyy; dfs(cur+1,m,len2); break; } } if(j==cur⑴) dfs(cur+1,m,len2); vis[i]=0; } } }

------分隔线----------------------------

下一篇 MySQL服务无法启动（2003 - Can't connect to MySQL server on‘localhost' (10061).）

------分隔线----------------------------