CF1036A Function Height 题解
2024-09-05 20:32:20
Content
给定一个坐标系,在它的 \(x\) 轴上有 \(2n+1\) 个点 \(P_0,P_1,P_2,...,P_{2n}\),其中对于 \(0\leqslant i\leqslant 2n\),有 \(OP_i\) 的长度为 \(i\)。可以执行一些操作,每次操作可将一个下标为奇数的点向上移动 \(1\) 个单位,这样进行若干次操作后会形成一些三角形。现在想让所有三角形的总面积为 \(k\),试求出当中的所有三角形的高的最小值。
数据范围:\(1\leqslant n,k\leqslant 10^{18}\)。
Solution
这题目确实题意比较难懂,建议去看下原题面给的图。
这样的话,将 \(P_0P_2,P_2P_4,...,P_{2n-2}P_{2n}\) 顺次连接起来,就可以获得 \(n\) 条长度为 \(2\) 的线段,又因为想要面积为 \(k\),所以,设所有三角形的高的总和为 \(h\),则 \(2\times h\times\dfrac{1}{2}=k\),解得 \(h=k\)。所以,我们就相当于将奇数下标的点往上移动 \(k\) 次了。
由于又想让高度最小,所以我们考虑尽量平均地分配每个点上移的高度。
很显然,如果 \(n\mid k\) 的话,那么我们正好将其均分给每一个三角形,那么答案就是 \(\dfrac{k}{n}\),否则,总会有多的一些没分到,那么就再尽量平均地分给 \(k\mod n\) 个三角形,所以答案就是 \(\dfrac{k}{n}+1\)。
综上,答案为 \(\begin{cases}\frac{k}{n}&n\mid k\\\frac{k}{n}+1&n\nmid k\end{cases}\)。
Code
ll n, m, ans;
int main() {
getll(n), getll(m);
ans = (!(m % n) ? m / n : m / n + 1);
writell(ans);
return 0;
}
最新文章
- pythonchallenge 解谜 Level 1
- CompletionService/ExecutorCompletionService/线程池/concurrent包
- lua的私有性(privacy)
- php array_udiff_uassoc比较数组的键值与值
- MySQL的left join中on与where的区别
- 深入分析windows下配置wamp环境各模块的版本兼容性
- ALM11需求和测试覆盖率图解1
- bzoj2893
- 利用SQL语句产生分组序号
- ueditor插件 -- 插入填空题
- Google Code Jam Round 1C 2015 Problem A. Brattleship
- ActiveMQ in Action(4) - Security
- 采用SmartQQ 协议可制作聊天机器人
- Mac OS X L2TP Client Setup
- .NET MVC后台发送post请求
- June 3. 2018 Week 23rd Sunday
- 【Core Swagger】.NET Core中使用swagger
- java导出json格式文件
- tf中的run()与eval()【转载】
- Linux进程的创建函数fork()及其fork内核实现解析【转】
热门文章
- Spring Cloud Gateway修改请求和响应body的内容
- C/C++ Qt Tree与Tab组件实现分页菜单
- 洛谷 P3700 - [CQOI2017]小Q的表格(找性质+数论)
- 洛谷 P5249 - [LnOI2019]加特林轮盘赌(期望 dp+高斯消元)
- STL的equal_range()
- 【讲座】詹显全——Proteoforms在肿瘤中应用
- Perl哈希%hash
- 基于python win32setpixel api 实现计算机图形学相关操作
- 在 Qualys SSL Labs SSL 测试中获得 A+ 评级的秘技 2021 版
- 【leetcode】721. Accounts Merge(账户合并)