首页 > 其他 > 详细

Codeforces Round #266 (Div.2) B Wonder Room --枚举

时间:2014-09-13 10:33:54      阅读:320      评论:0      收藏:0      [点我收藏+]

题意:给出一个两边长为a,b的矩形,要求增加a和增加b使a*b>=6*n且a*b最小。

解法:设新的a,b为a1,b1,且设a<b,那么a<=a1<=ceil(sqrt(6*n)),那么我们可以枚举a1,然后算出b1,如果b1<b,那么b1 = b,然后算出面积,取所有面积的最小值不就可以了,然后再枚举一次b1,处理与之相同即可。

复杂度O(sqrt(n))

代码:

bubuko.com,布布扣
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define lll __int64
using namespace std;

int main()
{
    lll n,a,b;
    lll mini,a1,b1;
    while(scanf("%I64d%I64d%I64d",&n,&a,&b)!=EOF)
    {
        mini = (1LL<<62);
        lll sum = (lll)6*n;
        for(lll i=a;i<=a+50000LL;i++)
        {
            lll tb = sum/i + (sum%i!=0);
            tb = max(b,tb);
            lll tarea = i*tb;
            if(tarea < mini)
            {
                mini = tarea;
                a1 = i;
                b1 = tb;
            }
        }
        for(lll i=b;i<=b+50000LL;i++)
        {
            lll ta = sum/i + (sum%i!=0);
            ta = max(a,ta);
            lll tarea = i*ta;
            if(tarea < mini)
            {
                mini = tarea;
                a1 = ta;
                b1 = i;
            }
        }
        cout<<mini<<endl<<a1<<" "<<b1<<endl;
    }
    return 0;
}
View Code

 

Codeforces Round #266 (Div.2) B Wonder Room --枚举

原文:http://www.cnblogs.com/whatbeg/p/3969514.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!