[ACM] HDU 1006 解题报告
报告 解题 ACM HDU 1006
2023-06-13 09:15:31 时间
偶尔写写ACM水题还是挺好玩的。(好吧其实是老婆求助我才看滴)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1006
一开始看到这题的时候,感觉一天24小时60分钟60秒。把每一秒的最小指针角度记下来再搞个排序。
每个case二分搜一下就好啦。
结果发现最后一个case的结果始终是错的。
后来才发现,原来这不是没秒动一下的,是所有的指针都是时时刻刻都在转的。就不能这么暴力地枚举啦。得讲究一点点数学方法啦。
于是,可以简化问题。假设时钟静止,其他指针相对于时针的速度什么的都算得出来啦。
思路如下:
- 首先,一天每12小时,三个指针会重复一次,所以只要算12小时就可以啦。
- 其次,每12小时,时针走了1圈,秒针走了 12×60圈,那么相对于时针秒针走了 (12×60−1)圈
- 然后,在秒针相对于时针走的每一圈里,分别有三种情况
- 秒针处于分针前且分针在时针前
- 秒针处于时针前且分针处于时针后(大于60度)
- 秒针处于分针后
对于每种情况,分别计算符合角度条件的时间,然后累加即可。
源码如下:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <memory>
#include <limits>
int main() {
double d;
const double& seconds_in_half_day = 12.0 * 60.0;
// ==========================================
while (scanf("%lf", &d) != EOF && d >= 0.0) {
// 每12小时秒针转12 * 60圈
// 每12小时时针转1圈
// 每12小时秒针追上时针12 * 60 - 1次
double cur_m_d = 0.0; // 当前分针度数
double sum_degree = 0.0;
// 以时针为原点,秒针每秒转 719/120°,每°要消耗120/719秒
// 以时针为原点,分针每秒转 11/120°,分针度数 = cur_m_d + 秒针度数 * 11 / 719
// 以时针为原点,秒针共转 12 * 60 - 1 圈
for (int i = 0; i < 12 * 60 - 1; ++i) {
// 1. 秒针在分针前, 分针在时针前
// cur_m_d + s * 11 / 719 - s >= d => s <= (cur_m_d - d) * 719 / 708
// d <= s
// 360 - (cur_m_d + s * 11 / 719) >= d => s <= (360 - cur_m_d - d) * 719 / 11
double s_d = (cur_m_d - d) * 719 / 708;
s_d = std::min<double>(s_d, (360.0 - cur_m_d - d) * 719 / 11);
if (s_d >= d)
sum_degree += s_d - d;
// 2. 秒针在分针前, 分针在时针后
// d <= s
// 360 - s >= d => s <= 360 - d
// (cur_m_d + s * 11 / 719) - 360 >= d => s >= (360 + d - cur_m_d) * 719 / 11
s_d = (360 + d - cur_m_d) * 719 / 11;
s_d = std::max<double>(s_d, d);
if (s_d <= 360 - d)
sum_degree += 360 - d - s_d;
// 3. 秒针在分针后
// s - (cur_m_d + s * 11 / 719) >= d => s >= (d + cur_m_d) * 719 / 708
// cur_m_d + s * 11 / 719 >= d => s >= (d - cur_m_d) * 719 / 11
// 360 - s >= d => s <= 360 - d
s_d = (d + cur_m_d) * 719 / 708;
s_d = std::max<double>(s_d, (d - cur_m_d) * 719 / 11);
if (s_d <= 360 - d)
sum_degree += 360 - d - s_d;
cur_m_d += 360.0 * 11 / 719;
while (cur_m_d >= 360.0)
cur_m_d -= 360.0;
}
printf("%.03lf\n", sum_degree * 100.0 / (12 * 60 - 1) / 360.0);
}
return 0;
}
解题说明
以时针为原点,秒针每秒转
, 每°要消耗
秒
以时针为原点,分针每秒转
,
以时针为原点,秒针共转
令 cur_m_d 为每圈分钟起始度数,d为输入的最小角度,s为秒针度数。
- 秒针在分针前, 分针在时针前
- 秒针在分针前, 分针在时针后
- 秒针在分针后
相关文章
- 《2022年上半年游戏安全洞察报告》发布:外挂肆虐,内容安全问题依旧严峻
- 字节高级码农年薪823万元,美国程序员收入报告出炉!
- 上海数字大脑研究院首次发布《2022上半年度人工智能行业报告》,多层面深度分析全球AI发展
- 《调研报告》:提振经济与风险并存的城市消费券
- 腾讯课堂双11消费趋势报告出炉!超百万人同时涌入,人均学习时长增长50%
- 卡巴斯基:2022年游戏相关网络威胁报告
- 天猫淘宝企业服务为中小微企业打造供应链智能协同网络,让采购不再将就!丨爱分析报告
- POJ 2606 Rabbit hunt 2780 Linearity 1118 Lining Up 解题报告
- 因子和——解题报告
- 《2022 企业数据安全能力建设现状研究报告》调研启动
- 报告Linux系统挂载状况报告(linux挂载情况)
- 报告利用Linux MTR报告进行网络质量分析(linuxmtr)
- 日本报告首例“拉姆达”变异毒株感染病例
- 迈克菲报告指出网络威胁情报共享的阻碍
- Linux系统设计与实施研究(linux设计报告)
- 2017年一季度区块链报告:监管机构极大地影响了全球市场
- MySQL报告:详细分析最新数据库趋势及性能优化技巧(mysql报告)
- Oracle AWR报告机会来了(oracle awr生成)
- Redis获取随机数进展缓慢一篇实证报告(redis获取随机数很慢)