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ǎ崽 阅读(5319)
评论(1) 编辑 收藏 引用