专栏首页owent[ACM] HDU 1006 解题报告

[ACM] HDU 1006 解题报告

偶尔写写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;
}

解题说明

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis全异步(HA)Driver设计稿

    现在Redis的集群功能已经Release。但是并没有一个官方直接提供的高可用性的API可以使用。有的只有解决方案,Sentinel和Cluster。所以有必要...

    owent
  • tolua++内存释放坑

    tolua++在new一个类的时候,会把类指针作为userdata传入lua,建立metatable并通过tolua_classevents函数给metatab...

    owent
  • [WP Code Highlight.js] Project

    https://github.com/owt5008137/WP-Code-Highlight.js

    owent
  • 初识I/O | I/O系列(一)

    I/O设备,包括磁盘、键盘、显示器、各种网络传输设备、及各种驱动程序等。计算机系统参与I/O的外设大体分为三类:

    搬砖俱乐部
  • 腾讯产品经理现身说法:to b的产品经理和to c产品经理区别

    用户1756920
  • How to Maintain a Website and Web Server?

    How-to-Maintain-a-Website-and-Web-Server-.png

    用户4822892
  • win10 使用 SMB v1

    原因是 SMB1 是不安全的,所以微软在 win10 系统就不给使用,如果需要使用,需要使用管理员打开 Powershell 输入下面代码

    林德熙
  • 阻击外挂:《龙之谷手游》安全测试的那点事

    手游的使用场景与传统APP有着巨大的差异,不同的游戏玩法, 技术实现都不一样,因此手游安全测试团队需要对每一个游戏,都从零开始研究游戏内部实现架构。近期腾讯推出...

    WeTest质量开放平台团队
  • 阻击外挂——《龙之谷手游》安全测试的那点事

    随着智能手机的全面普及和市场泛娱乐化,移动游戏行业发展迅猛,无论是市场收入还是用户规模,手游在游戏市场上已经占据了半壁江山。如此火热的市场吸引了大量外挂、辅助工...

    WeTest质量开放平台团队
  • 我所相信的未必可信

    王兵

扫码关注云+社区

领取腾讯云代金券