【非原创】codeforces 1029F Multicolored Markers 【贪心+构造】
2024-09-01 08:57:35
题目:戳这里
题意:给a个红色小方块和b个蓝色小方块,求其能组成的周长最小的矩形,要求红色或蓝色方块至少有一个也是矩形。
思路来源:戳这里
解题思路:遍历大矩形可能满足的所有周长,维护最小值即可。需要注意蓝色或红色只要有一种矩形能放进大矩形中,则这个大矩形一定满足条件,小矩形放左下角,另一个颜色补缺就行了。
具体看代码。
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <string>
5 #include <vector>
6 #include <map>
7 #include <cmath>
8 #include <iostream>
9 using namespace std;
10 typedef long long ll;
11 const int maxn = 1e6 + 10;
12 int n;
13 int na[maxn];
14 int main()
15 {
16 ll a, b;
17 scanf("%lld %lld", &a, &b);
18 ll sum = a + b;
19 ll ans = 2 * (a + b + 1);
20 ll minn = a + b;
21 for(ll i = 1; i * i <= sum; ++i)
22 {
23 if(a % i == 0) minn = min(minn, a / i);
24 if(b % i == 0) minn = min(minn, b / i);//minn就是用来找到那个能放进去的小矩形
25 if((a + b) % i == 0 && minn <= (a + b) / i) ans = min(ans, 2 * ((a + b) / i + i));//维护合理的大矩形周长
26 }
27 printf("%lld\n", ans);
28 return 0;
29 }
最新文章
- 【夯实PHP基础】PHP的反射机制
- HAOI2015 泛做
- phpcms V9 内容模型管理
- 在Virtulbox上装Ubuntu
- 人民币大写金额转换C#方法
- STL库函数 持续更新
- Excel 中单元格和范围的引用(即访问的表示方法)
- matlab 画框(一)
- Eclipse 4.6 Neon, could not create the java virtual machine
- ubuntu common
- Struts数据效验
- 关于SQL语言分类
- Excel中VBA 连接 数据库 方法- 摘自网络
- PGA与SGA
- [转]Centos6.5使用yum安装mysql—配置MySQL允许远程登录
- 看完让你彻底搞懂Websocket原理
- 初窥图像识别与k-means算法
- 原生 table css实现操作按钮固定右侧及底部滚动 IE不会卡死
- BZOJ 1706
- python 函数赋值
热门文章
- windows下如何安装Python、pandas
- Zabbix监控虚拟机服务-告警与自动恢复-模板化
- 前端面试之HTTP
- 研发流程 接口定义&;开发&;前后端联调 线上日志观察 模型变动
- net.core.somaxconn net.ipv4.tcp_max_syn_backlog
- Java NIO ———— Buffer 缓冲区详解 入门
- UI自动化测试实战
- Web信息收集之搜索引擎-Shodan Hacking
- Quartz:定时任务工具类
- Poem 01(转)