How Big Is It?

How Big Is It?

时间: 1ms        内存:64M

描述:

Ian is going to California and has to pack his things, including his collection of circles. Given a set of circles, your program must find the smallest rectangular box they fit in.

All circles must touch the bottom of the box. The figure below shows an acceptable packing for a set of circles, although it may not be the optimal packing for these particular circles. In an ideal packing, each circle should touch at least one other circle, but you probably figured that out.

输入:

The first line of input contains a single positive decimal integer n, n <= 50. This indicates the number of test cases to follow. The subsequent n lines each contain a series of numbers separated by spaces. The first number on each of these lines is a positive integer m, m <= 8, which indicates how many other numbers appear on that line. The next m numbers on the line are the radii of the circles which must be packed in a single box. These numbers need not be integers.

输出:

For each test case, your program must output the size of the smallest rectangle which can pack the circles. Each case should be output on a separate line by itself, with three places after the decimal point. Do not output leading zeroes unless the number is less than 1, e.g., 0.543.

示例输入:

3
3 2.0 1.0 2.0
4 2.0 2.0 2.0 2.0
3 2.0 1.0 4.0

示例输出:

9.657
16.000
12.657

提示:

参考答案(内存最优[1792]):

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
double a[10], p[10];
void fun(int n)
{
    double x=0;
    for(int i=0; i<n; i++)
    {
        x=2*sqrt(a[i]*a[n]);
        p[n]=max(p[n],x+p[i]);
    }
}
int main()
{
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d", &m);
        for(int i=0; i<m; i++)
            scanf("%lf", &a[i]);
        sort(a,a+m);
        double ans =0xffffff,tmp;
        do
        {
            memcpy(p,a,sizeof(a));
            for(int i=1; i<m; i++)fun(i);
            tmp = 0;
            for(int i=0; i<m; i++)tmp=max(tmp,p[i]+a[i]);
            ans = min(ans, tmp);
        }
        while(next_permutation(a,a+m));
        printf("%.3lf\n",ans);
    }
    return 0;
}

参考答案(时间最优[0]):

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
double a[10], p[10];
void fun(int n)
{
    double x=0;
    for(int i=0; i<n; i++)
    {
        x=2*sqrt(a[i]*a[n]);
        p[n]=max(p[n],x+p[i]);
    }
}
int main()
{
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d", &m);
        for(int i=0; i<m; i++)
            scanf("%lf", &a[i]);
        sort(a,a+m);
        double ans =0xffffff,tmp;
        do
        {
            memcpy(p,a,sizeof(a));
            for(int i=1; i<m; i++)fun(i);
            tmp = 0;
            for(int i=0; i<m; i++)tmp=max(tmp,p[i]+a[i]);
            ans = min(ans, tmp);
        }
        while(next_permutation(a,a+m));
        printf("%.3lf\n",ans);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注