Codeforces Round #506 (Div. 3)(F. Multicolored Markers)

链接:https://codeforces.com/contest/1029/problem/F
思路:i从1开始到根号(a+b)进行遍历,维护一个最小值,当某个值是a或b的因子时,更新这个最小值为(a或者b)/i,表示要放一个矩形在里面所需要的最小的边,如果当(a+b)%i==0时且最小值小于(a+b)/i,就表示可以放下一个矩形,从而更新一下周长的最小值,一直到遍历结束即可。这个题必须要这样从小到大遍历,不然将面临一个大矩形里面放能否放一个a或者b的矩形这样的问题,无法在常数的时间内解决,复杂度会加一个维度,从小到达遍历保证每一种能放的情况都考虑到了,从而一定会找到最优解。
代码:

#include<bits/stdc++.h>
using namespace std;

long long a,b;

int main(){
    scanf("%I64d%I64d",&a,&b);
    long long i = sqrt(a+b+0.1);
    long long minv = 1e18,res = 1e18;
    for(long long j=1;j<=i;j++){
        if(a%j==0)minv = min(minv,a/j);
        if(b%j==0)minv = min(minv,b/j);
        if((a+b)%j==0&&minv<=(a+b)/j)res  = min(res,2*j+2*(a+b)/j);
    }
    printf("%I64d\n",res);
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 专业考题类型管理运行工作负责人一般作业考题内容选项A选项B选项C选项D选项E选项F正确答案 变电单选GYSZ本规程...
    小白兔去钓鱼阅读 9,051评论 0 13
  • 选择题部分 1.(),只有在发生短路事故时或者在负荷电流较大时,变流器中才会有足够的二次电流作为继电保护跳闸之用。...
    skystarwuwei阅读 13,291评论 0 7
  • 飘荡浮云阅读 131评论 0 0
  • 周二到周五 下午 周六 全天 不需要跑步 都是静态测试 唯一耗费体力的就是女性仰卧起坐和男性俯卧撑 有点价值的项目...
    nichinichi阅读 262评论 0 2