学海泛舟

codeforces contest449 A Jzzhu and Chocolate 题解

发表于 | 分类于 |

原题

传送门

题目大意

给一块n*m的巧克力，要切k刀（只能沿个分割线切，即横着切或竖着切），问切完后，最小的那块的最大面积是多少

分析

为使最小的面积最大，无论在行还是列，我们都应该尽量等分。
那么，最小面积的表达式就不难列出了，area=(n/x)(m/y)（这里的除法都是地板除），其中x表示被分成了x行，y表示被分成了y列，剩下的问题是如何求出面积的最大值。
基于x+y=k+2这个等式，我们不难发现，倘若n/x（m/y）固定时，只要使x（y）尽可能大，那么area就会取到当前的最大值。
那么我们就先枚举n/x的值，x的取值范围是[1,n]，n/x的值的个数一定是小于2sqrt(n)，所以枚举这个想法在时间复杂度是可行的。然后我们再枚举m/y的值，不断更新area的值，最后就能得到最小的最大面积了。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
int main(){
	LL n,m,k;
	LL ans=0;
	scanf("%I64d %I64d %I64d",&n,&m,&k);
	if(n+m<k+2) {
		puts("-1");
		return 0;
	}
	int i;
	for(i=1;i<=n/i&&i<k+2;i++){
		ans=max(ans,(n/i)*(m/(k+2-i)));
	}
	for(i=n/i;i>=1&&n/i<k+2;i--){
		ans=max(ans,i*(m/(k+2-n/i)));
	}
	for(i=1;i<=m/i&&i<k+2;i++){
		ans=max(ans,(m/i)*(n/(k+2-i)));
	}
	for(i=m/i;i>=1&&m/i<k+2;i--){
		ans=max(ans,i*(n/(k+2-m/i)));
	}
	printf("%I64d\n",ans);
	return 0;
}