题目描述
wls有一个钟表,当前钟表指向了某一个时间。
又有一些很重要的时刻,wls想要在钟表上复现这些时间(并不需要依次复现)。我们可以顺时针转动秒针,也可以逆时针转动秒针,分针和时针都会随着秒针按规则转动,wls想知道秒针至少转动多少角度可以使每个时刻至少都会被访问一次。
注意,时钟上的一种时针分针秒针的组合,可以代表两个不同的时间。
又有一些很重要的时刻,wls想要在钟表上复现这些时间(并不需要依次复现)。我们可以顺时针转动秒针,也可以逆时针转动秒针,分针和时针都会随着秒针按规则转动,wls想知道秒针至少转动多少角度可以使每个时刻至少都会被访问一次。
注意,时钟上的一种时针分针秒针的组合,可以代表两个不同的时间。
输入
第一行一个整数n代表有多少个时刻要访问。
第二行三个整数h,m,s分别代表当前时刻的时分秒。
最后n行每一行三个整数hi,mi,si代表每个要访问的时刻的时分秒。
1≤n≤86,400
0≤h,hi<24
0≤m,mi,s,si<60
第二行三个整数h,m,s分别代表当前时刻的时分秒。
最后n行每一行三个整数hi,mi,si代表每个要访问的时刻的时分秒。
1≤n≤86,400
0≤h,hi<24
0≤m,mi,s,si<60
输出
输出一行一个数代表秒钟转的角度,答案保留两位小数。
样例输入
1
0 1 0
0 1 1
样例输出
6.00
【题解】
我把这个环复制了三个,把每一个时刻当作环上的每一个点,把环展开成三份。
分三种情况:
1、全往顺时针,或者全往逆时针。
2、先往顺时针,再往逆时针。
3、先往逆时针,再往顺时针。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 3e5+10; 4 const int M = 43200 ; 5 int a[N],n; 6 int main() 7 { 8 9 //cout << -1 % 10 << endl ; 10 ios_base :: sync_with_stdio(false); 11 cin.tie(NULL) , cout.tie(NULL); 12 int h , mi , s ; 13 cin >> n ; 14 cin >> h >> mi >> s ; 15 int Start = h * 3600 + mi * 60 + s ; 16 if( Start >= M ) Start -= M ; 17 int m = 0 ; 18 19 //cout << "####" << endl; 20 21 for( int i = 0,u,v,w ; i<n ; i++ ){ 22 cin >> u >> v >> w ; 23 int tmp = (u * 3600 + v * 60 + w) ; 24 if( tmp >= M ) tmp -= M ; 25 if( Start == tmp ) continue ; 26 else { 27 a[m++] = tmp ; 28 } 29 } 30 31 sort( a , a + m ); 32 33 for( int i = 0 ; i < m ; i++ ){ 34 a[i+m] = a[i] + 43200 ; 35 a[i+2*m] = a[i] + 86400 ; 36 } 37 if( m == 0 ){ 38 //printf("####\n"); 39 printf("0.00\n"); 40 }else{ 41 int L = m+10 , R = m+10 ; 42 Start += 43200 ; 43 //printf("###\n"); 44 for( int i = 0 ; i < 3 * m ; i++ ){ 45 if( a[i] < Start && Start < a[i+1] ){ 46 L = i , R = i + 1 ; 47 break ; 48 } 49 } 50 //printf("( %d , %d ) , a[L] = %d , a[R] = %d \n",L,R,a[L],a[R]); 51 52 //printf("%d , %d \n", L , R ) ; 53 int t1 = (Start-a[L]) >= M ? (Start-a[L]) - M : Start-a[L] ; 54 int t2 = (a[R]-Start) >= M ? (a[R]-Start) - M : a[R]-Start ; 55 //t1 = ( t1 + M ) % M ; 56 //t2 = ( t2 + M ) % M ; 57 //printf("%d\n",M); 58 //printf("%d %d\n",t1,t2) ; 59 //printf("%d %d\n",M - t1 , M - t2 ); 60 int ans = min( (M - t1) , (M - t2) ); 61 //printf("%d %d - %d = %d , %d - %d = %d \n",ans, Start , a[L] , (Start-a[L]) , a[R] , Start , (a[R]-Start) ); 62 //printf("%d\n",ans); 63 for( int i = L ; L - m + 1 < i ; i-- ){ 64 ans = min( ans , (Start - a[i]) * 2 + a[i+m-1] - Start ); 65 } 66 for( int i = R ; i < R + m - 1 ; i++ ){ 67 ans = min( ans , (a[i] - Start) * 2 + Start - a[i-m+1] ); 68 } 69 ans = ans * 6 ; 70 printf("%d.00\n",ans); 71 } 72 return 0; 73 }