「Codeforces 1029F」Multicolored Markers

发表于 | | 阅读次数:
字数统计: 493 字

Description

题目链接：Codeforces 1029F

有一个由正方形砖块组成的板子（你可以认为是无限大的），你需要将 $a$ 个格子染成红色，$b$ 个格子染成蓝色。最终有颜色的砖块要形成一个大小为 $a+b$ 的矩形，并且其中至少有一种颜色也需要形成一个矩形。求出所有染色方案中，有颜色的砖块组成的矩形的周长最小值。

数据范围：$1\le a,b\le 10^{14}$

Solution

我们可以发现，如果忽略染色的情况，那么矩形的形态总共有 $O(\sqrt{a+b})$ 个。对于这个数据范围，我们显然可以枚举矩形的较短边的长度 $i$。根据贪心的思路，我们从大到小枚举，遇到第一个满足条件的 $i$ 就可以得到最优解 $2\times(i+\frac{a+b}{i})​$。

接下来的问题就是如何判断是否可以将某一种颜色形成一个矩形。此时我们也可以贪心，假设需要染成矩形的颜色有 $a$ 个，那么我们找到最大的 $j$ 满足 $j\le i$ 并且 $j\mid a$。如果 $\frac{a}{j}\le \frac{a+b}{i}$ 那么就说明满足条件。

我们又可以发现这个 $j$ 是单调的，所以可以 $O(\sqrt a)$ 求出 $a$ 的因子，直接用一个指针移动就能找到当前最大的 $j$ 了。

时间复杂度：$O(\sqrt a)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <cstdio>
#include <algorithm>
#include <vector>

long long solve(long long tot,long long a) {
    std::vector<int> f;
    for(int i=1;1LL*i*i<=a;++i) if(a%i==0) f.push_back(i);
    int p=(int)f.size()-1;
    for(int i=sqrt(tot);i>=1;--i) {
        if(tot%i) continue;
        while(f[p]>i) --p;
        if(a/f[p]<=tot/i) return 2LL*(i+tot/i);
    }
    return 1LL<<60;
}
int main() {
    long long n,m;
    scanf("%lld%lld",&n,&m);
    printf("%lld\n",std::min(solve(n+m,n),solve(n+m,m)));
    return 0;
}
0%