Gym

题意：有n个时钟，只能顺时针拨，问使所有时间相同的最小代价是多少

思路：将时间排序，枚举拨动到每一个点的时间就好了，容易证明最终时间一定是其中之一

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 #define MAXN 200005
18 #define U 1000000
19 using namespace std;
20 LL t[MAXN], sum1[MAXN], sum2[MAXN];
21 int main()
22 {
23 #ifndef ONLINE_JUDGE
24     freopen("in.txt", "r", stdin);
25     //freopen("out.txt", "w", stdout);
26 #endif // OPEN_FILE
27     int n;
28     memset(t, 0, sizeof(t));
29     memset(sum1, 0, sizeof(sum1));
30     memset(sum2, 0, sizeof(sum2));
31     LL x, y, z;
32     scanf("%d", &n);
33     for(int i = 1; i <= n; i++){
34         scanf("%I64d%I64d%I64d", &x, &y, &z);
35         t[i] = (x * U + y) * U + z;
36     }
37     sort(t + 1, t + n + 1);
38     for(int i = 1; i <= n; i++){
39         sum1[i] = sum1[i - 1] + t[i];
40     }
41     for(int i = n; i >= 1; i--){
42         sum2[i] = sum2[i + 1] + t[i];
43     }
44     LL ans;
45     bool flag = false;
46     LL ALL = 1000000LL * 1000000LL * 12LL;
47     for(int i = 1; i <= n; i++){
48         LL res = (i - 1) * t[i] - sum1[i - 1] + ALL * (n - i) - (sum2[i + 1] - (n - i) * t[i]);
49         if(!flag){
50             ans = res;
51             flag = true;
52         }
53         else{
54             ans = min(ans, res);
55         }
56     }
57     LL s = ans % U;
58     ans = ans / U;
59     LL m = ans % U;
60     ans = ans / U;
61     LL h = ans;
62     printf("%I64d %I64d %I64d
", h, m, s);
63 }