枚举+数学，CF 449A - Jzzhu and Chocolate

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

A - Jzzhu and Chocolate

二、解题报告

1、思路分析

我们考虑横着切 x 次，那么得到的巧克力块中最小宽应该是 n / (x + 1)

而 x 最大是n - 1，n / (x + 1) 的取值是 sqrt(n) 级别的

那么我们可以枚举最小宽，由宽推出横切的次数，剩下的次数全给竖切

维护答案即可

2、复杂度

时间复杂度： O(sqrt(n))空间复杂度：O(n)

3、代码详解

 ​

#include <bits/stdc++.h>

// #define DEBUG

using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

void solve(){
	int n, m, k;
	std::cin >> n >> m >> k;

	i64 res = 0;

	auto f = [&](int x) -> int {
		return m / std::max(1, (x + 1));
	};

	for (int i = 1; i <= n && i <= 40000; ++ i) {
		res = std::max(res, 1LL * i * f(k - n / i + 1));
		res = std::max(res, 1LL * n / i * f(k - n / (n / i) + 1));
	}

	std::cout << (res ? res : -1);
}

auto FIO = []{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	return 0;
}();

int main() {
	#ifdef DEBUG
		freopen("in.txt", 'r', stdin);
		freopen("out.txt", 'w', stdout);
	#endif
	int t = 1;
	// std::cin >> t;
	while(t --)
		solve();
	return 0;
}