http://acm.hdu.edu.cn/showproblem.php?pid=1006第一版為數(shù)不多的過的人很少的題目
一直是心結(jié)
前幾天打算刷光第一版的題目
于是思考了一下
方法是馬上就出來了
今天打算實(shí)現(xiàn)，寫了好久，差不多半天了
首先是三個(gè)針角度的函數(shù)：
秒針：6t
分針：(t%60)/10
時(shí)針：(t%3600)/120
a是題目給你的限制時(shí)間
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
時(shí)間只要滿足上市就是happytime
由于double類型不好取mod
我就把時(shí)間分割成一分鐘一分鐘
循環(huán)個(gè)720次。。。。所以說這樣的方法比較暴力
不過據(jù)說有循環(huán)，不過我想不出來。。。
然后就只計(jì)算上邊三個(gè)式子的交集。。。
浮點(diǎn)型的交集好煩。。
#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
//計(jì)算同時(shí)滿足上邊三個(gè)條件的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ǎ崽 閱讀(5320)
評(píng)論(1) 編輯 收藏 引用