随笔-72  评论-126  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=1006

第一版为数不多的过的人很少的题目
一直是心结
前几天打算刷光第一版的题目
于是思考了一下
方法是马上就出来了
今天打算实现,写了好久,差不多半天了
首先是三个针角度的函数:
秒针:6t
分针:(t%60)/10
时针:(t%3600)/120

a是题目给你的限制时间
 a <= | 6*t-(t%60)/10| <= 360-a
 a <= | 6*t-(t%3600)/120 | <= 360-a
 a <= | (t%60)/10-(t%3600)/120 | <= 360-a
时间只要满足上市就是happytime

由于double类型不好取mod
我就把时间分割成一分钟一分钟
循环个720次。。。。所以说这样的方法比较暴力
不过据说有循环,不过我想不出来。。。

然后就只计算上边三个式子的交集。。。
浮点型的交集好烦。。

#include<stdio.h>
#include
<stdlib.h>
#include
<string>
double num[14];
int hash[13];
int cmp(const void *a,const void *b)
{
    
return *(double *)a > *(double *)b ? 1 : -1;
}
void hh(double a ,double b)
{
    
int i;
    
double start,end;
    start 
= 0;
    end 
= a;
    
for(i=0;i<13;i++)
        
if(start <= num[i] && num[i+1<= end)
            hash[i] 
++;
    start 
= b;
    end 
= 60;
    
for(i=0;i<13;i++)
        
if(start <= num[i] && num[i+1<= end)
            hash[i] 
++;
}
void hhh(double a,double b)
{
    
int i;
    
if(b<0 || a>60)
        
return ;
    
for(i=0;i<13;i++)
        
if(a <= num[i] && num[i+1<= b)
            hash[i] 
++;
}
double happytime(double ms,double hs,double a)
{
    
//a <= | 6*t-(t+ms)/10 | <= 360-a
    
    
//a <= | 6*t-(t+hs)/120 | <= 360-a
    
    
//a <= | (t+ms)/10-(t+hs)/120 | <= 360-a
    
    
//计算同时满足上边三个条件的t
    double aa,ab,ac,ad,ba,bb,bc,bd,ca,cb,cc,cd,sum;
    
    aa 
= (ms-a*10)/59;
    ab 
= (ms+a*10)/59;
    ac 
= (ms+10*a-3600)/59;
    ad 
= (ms+3600-10*a)/59;

    ba 
= (hs-12*ms-a*120)/11;
    bb 
= (hs-12*ms+a*120)/11;
    bc 
= (hs-12*ms+120*a-43200)/11;
    bd 
= (hs-12*ms+43200-120*a)/11;

    ca 
= (hs-a*120)/719;
    cb 
= (hs+a*120)/719;
    cc 
= (hs+120*a-43200)/719;
    cd 
= (hs+43200-120*a)/719;

    num[
0= 0;
    num[
1= 60;
    num[
2= aa;
    num[
3= ab;
    num[
4= ac;
    num[
5= ad;
    num[
6= ba;
    num[
7= bb;
    num[
8= bc;
    num[
9= bd;
    num[
10= ca;
    num[
11= cb;
    num[
12= cc;
    num[
13= cd;

    qsort(num,
14,sizeof(num[0]),cmp);
    memset(hash,
0,sizeof(hash));
    sum 
= 0;
    hh(aa,ab);
    hh(ba,bb);
    hh(ca,cb);
    hhh(ac,ad);
    hhh(bc,bd);
    hhh(cc,cd);
    
for(int i=0;i<13;i++)
        
if(hash[i]>=6)
            sum 
+= num[i+1- num[i];
    
return sum;
}
int main()
{
    
int i,start;
    
double ans,a;
    
while(scanf("%lf",&a),a!=-1)
    {
        ans 
= 0;
        start 
= 0;
        
for(i=0;i<720;i++)
        {
            
if(i==109)
                i 
= i;
            ans 
+= happytime(start%3600,start,a);
            start 
+= 60;
        }
        printf(
"%.3lf\n",ans*100/43200);
    }
    
return 0;
}


整了好久。。。。
过了sample后就AC了。呵呵
posted on 2009-03-10 20:17 shǎ崽 阅读(5022) 评论(1)  编辑 收藏 引用

评论:
# re: hdoj1006~~Tick and Tick 2009-11-28 01:01 | xujiazhe
hao!  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理