当前位置: 首页> 文旅> 酒店 > 枚举+数学,CF 449A - Jzzhu and Chocolate

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

时间:2025/7/11 0:29:14来源:https://blog.csdn.net/EQUINOX1/article/details/141903385 浏览次数:0次

目录

一、题目

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 DEBUGusing 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 DEBUGfreopen("in.txt", 'r', stdin);freopen("out.txt", 'w', stdout);#endifint t = 1;// std::cin >> t;while(t --)solve();return 0;
}

关键字:枚举+数学,CF 449A - Jzzhu and Chocolate

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: