HDU/1006

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Tick and Tick	★★☆☆☆	答案正确	100	2015-02-06 18:36:58	算法错误（0）

来自寒假练习：Only a signing tool ! G题
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1006

题意

在一天之内，求时、分、秒针之间相隔角度超过D度的时间占比例。

题解

这题也是神烦。

首先问题是秒针是离散地动还是连续地动，题目其实没有明确，"rotating every second"确实有暗示每秒地动，可是看数据它的确是连续得动。
如果是离散的动，那么枚举每一秒判断就好了，然后会WA（如果继续划分更精确的时间，会T）。
连续的动没什么头绪，就先计算：

对于从0点开始，每走过时间dt(s)，在半天内，0<=dt<43200那么

时针走过：dh= $\frac{dt}{3600*12}*360$ deg= $\frac{dt}{120}$ deg

分针走过：dm= $\frac{dt}{60*60}*360$ deg= $\frac{dt}{10}$ deg

秒针走过：ds= $\frac{dt}{60}*360$ deg=6dt deg

令dt=120t，于是

dh=t

dm=12t

ds=720t

令dt=120t，0<=t<360即

|dh-dm|=11t

|dh-ds|=719t

|dm-ds|=708t

得到满足条件为

D<11t mod 360<360-D

D<719t mod 360<360-D

D<708t mod 360<360-D

即

$\frac{360k1+D}{11}<t<\frac{360(k1+1)-D}{11}$

$\frac{360k2+D}{719}<t<\frac{360(k2+1)-D}{719}$

$\frac{360k3+D}{708}<t<\frac{360(k3+1)-D}{708}$

算到这里，时间就可以离散化到每一个k1,k2,k3对应的点，按时间从小到大分别判断即可。

代码

1006.cpp代码已折叠

展开折叠内容

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
    while(1)
    {
        double D;
        cin>>D;
        if(D<-.5f)
            return 0;
        double t,happtT=0,lt,happyTime=0;
        bool openHappy=0,minTo;
        int k[4]={};
        bool b[4]={};
        for(t=0;t<360;)
        {
            double uOpen[4]={
                0,
                (360*k[1]+D)/11,
                (360*k[2]+D)/708,
                (360*k[3]+D)/719
            },
               uEnd[4]=
            {
                0,
                (360*k[1]+360-D)/11,
                (360*k[2]+360-D)/708,
                (360*k[3]+360-D)/719
            };
            double minT=1e+9;
            int minTi;
            for(int i=1;i<=3;++i)
            {
                if(minT>=uOpen[i]-1e-9&&!b[i])
                    minT=uOpen[i],minTi=i,minTo=0;
                if(minT>=uEnd[i]-1e-9&&b[i])
                    minT=uEnd[i],minTi=i,minTo=1;
            }
            b[minTi]=!b[minTi];
            if(minTo)++k[minTi];
            if(b[1]&&b[2]&&b[3]&&!minTo)
            {
                lt=minT;openHappy=1;
            }
            if(minTo&&openHappy)
            {
                happyTime+=minT-lt;
                openHappy=0;
            }
            t=minT;
        }
        if(openHappy)
            happyTime+=360-lt;
        cout<<fixed<<setprecision(3)<<happyTime*100/360<<endl;
    }
}

HDU/1006

目录

摘要

题意

题解

代码

著作权声明[编辑]

关于[编辑]