首页 > 代码库 > HDU 1006 Tick and Tick 时钟指针问题
HDU 1006 Tick and Tick 时钟指针问题
Tick and Tick
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 10194 Accepted Submission(s): 2859
Problem Description
The three hands of the clock are rotating every second and meeting each other many times everyday. Finally, they get bored of this and each of them would like to stay away from the other two. A hand is happy if it is at least D degrees from any of the rest. You are to calculate how much time in a day that all the hands are happy.
Input
The input contains many test cases. Each of them has a single line with a real number D between 0 and 120, inclusively. The input is terminated with a D of -1.
Output
For each D, print in a single line the percentage of time in a day that all of the hands are happy, accurate up to 3 decimal places.
Sample Input
012090-1
Sample Output
100.0000.0006.251
思想：
由于要记录连续时间，那么就利用区间记录，[begin,end]。另外，就拿时针和分针来做例子吧。时针的角速度为w_h=360.0/12*60*60=1.0/120，分针的角速度为w_m=360.0/60*60=1.0/10。两者的相对角速度为w_hm=w_m-w_h，“相对周期”为T_hm=360.0/w_hm。所谓的相对周期就是时针和分针出现重复的相对关系的最小时间。
这样的话就可以把时针和分针，时针和秒针，分针和秒针各自满足条件的集合求交集。显然，代码中利用的是三个for循环来暴力解决。不过有些显然不满足条件的情况即可去除，以减少计算次数。
x[3]和y[3]记录的是第一个开始满足条件的时间和第一个开始不满足条件的时间。m[3],n[3]则是分表根据相对周期来扩大x[3],y[3]以获得所有满足条件的时间集合，并求交集。
代码：
#include<iostream>#include<iomanip>#include <algorithm>using namespace std;const double hm = 11.0/120, hs = 719.0/120, sm = 59.0/10; //相对角速度const double T_hm = 43200.0/11, T_hs = 43200.0/719, T_sm = 3600.0/59; //相对周期inline double min(double a,double b,double c){ double temp[3] = {a,b,c}; return *std::min_element(temp,temp+3);}inline double max(double a,double b,double c){ double temp[3] = {a,b,c}; return *std::max_element(temp,temp+3);}int main(){ double degree; double x[3],y[3]; double m[3],n[3]; double end,begin,sum; while(cin>>degree , degree!=-1) { x[0]=degree/hm; x[1]=degree/hs; x[2]=degree/sm; y[0]=(360-degree)/hm; y[1]=(360-degree)/hs; y[2]=(360-degree)/sm; sum=0.0; for(m[0]=x[0],n[0]=y[0];n[0]<=43200.000001;m[0]+=T_hm,n[0]+=T_hm) { for(m[1]=x[1],n[1]=y[1];n[1]<=43200.000001;m[1]+=T_hs,n[1]+=T_hs) { for(m[2]=x[2],n[2]=y[2];n[2]<=43200.000001;m[2]+=T_sm,n[2]+=T_sm) { begin=max(m[0],m[1],m[2]); end=min(n[0],n[1],n[2]); if(end>begin) sum+=end-begin; } } } cout<<setiosflags(ios::fixed)<<setprecision(3)<<sum*100.0/43200<<endl; } return 0;}
用库尼玛 超时自己实现比较
#include<iostream>#include<iomanip>using namespace std;const double hm=11.0/120,hs=719.0/120,sm=59.0/10; //相对角速度const double T_hm=43200.0/11,T_hs=43200.0/719,T_sm=3600.0/59; //相对周期inline double min(double a,double b,double c){ double temp=(a>b)?b:a; return (c>temp)?temp:c;}inline double max(double a,double b,double c){ double temp=(a>b)?a:b; return (c>temp)?c:temp;}int main(){ double degree; double x[3],y[3]; double m[3],n[3]; double end,begin,sum; while(cin>>degree , degree!=-1) { x[0]=degree/hm; x[1]=degree/hs; x[2]=degree/sm; y[0]=(360-degree)/hm; y[1]=(360-degree)/hs; y[2]=(360-degree)/sm; sum=0.0; for(m[0]=x[0],n[0]=y[0];n[0]<=43200.000001;m[0]+=T_hm,n[0]+=T_hm) { for(m[1]=x[1],n[1]=y[1];n[1]<=43200.000001;m[1]+=T_hs,n[1]+=T_hs) { if(n[0]<m[1]) break; if(m[0]>n[1]) continue; for(m[2]=x[2],n[2]=y[2];n[2]<=43200.000001;m[2]+=T_sm,n[2]+=T_sm) { if(n[0]<m[2] || n[1]<m[2]) break; if(m[0]>n[2] || m[1]>n[2]) continue; begin=max(m[0],m[1],m[2]); end=min(n[0],n[1],n[2]); if(end>begin) sum+=end-begin; } } } cout<<setiosflags(ios::fixed)<<setprecision(3)<<sum*100.0/43200<<endl; } return 0;}HDU 1006 Tick and Tick 时钟指针问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。