A. Nano alarm-clocks
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/gym/100637/problem/A
Description
An old watchmaker has n stopped nano alarm-clocks numbered with integers from 1 to n. Nano alarm-clocks count time in hours, and in one hour there are million minutes, each minute lasting a million seconds. In order to repair them all the watchmaker should synchronize the time on all nano alarm-clocks. In order to do this he moves clock hands a certain time forward (may be zero time). Let’s name this time shift a transfer time.
Your task is to calculate the minimal total transfer time required for all nano alarm-clocks to show the same time.
Input
The first line contains a single integer n — the number of nano alarm-clocks (2 ≤ n ≤ 105). In each i-th of the next n lines the time h, m,s, shown on the i-th clock. Integers h, m and s show the number of hours, minutes and seconds respectively. (0 ≤ h < 12, 0 ≤ m < 106,0 ≤ s < 106).
Output
Output three integers separated with spaces h, m and s — total minimal transfer time, where h, m and s — number of hours, minutes and seconds respectively (0 ≤ m < 106, 0 ≤ s < 106).
Sample Input
2
10 0 0
3 0 0
Sample Output
5 0 0
HINT
题意
给你n个时钟，只可向前拨 问你总计拨多少时间，可以使得所有表的时间一样
题解：
排序+维护前缀和，暴力出最小的就OK
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef __int64 ll;
using namespace std;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//**************************************************************************************
ll t=;
int n;
ll sum[];
ll a[];
int main()
{ scanf("%d",&n);
for(int i=; i<=n; i++)
{
ll h,m,s;
cin>>h>>m>>s;
a[i]=s+m*t+t*t*h;
}
sort(a+,a+n+);
for(int i=;i<=n;i++)
sum[i]=sum[i-]+a[i];
ll tt=*t*t;
ll ans=tt*;//此处无穷大就好了 for(int i=n;i>=;i--)
{
ll xx=(a[i]*(i-)-sum[i-]+(a[i]+tt)*(n-i)-(sum[n]-sum[i]));
ans=min(xx,ans);
}
printf("%I64d %I64d %I64d\n",(ans/t)/t,(ans/t)%t,ans%t);
return ;
}