我一直在尝试为一个在线裁判系统解决这个问题，它需要1000ms的时间限制。我尝试了几种不同的解决方案，但我会在这里发布我最好的草稿。我能够得到正确的答案，但是，我超过了时间限制。我能想出的最佳解决方案是 O(n^2)。
任务问题
有一次程序员 X 在中国，注意到俄罗斯的时钟“Zarya”比俄罗斯便宜 10 倍。X选择了一些恶作剧，购买了大量的时钟将其带到自己的国家并以半价出售（实际上是他购买的价格的5倍）。但一回到家，他就发现很多钟走的不和谐，而且，它们只是简单的推一下就停止了（或者如果它们之前被停止过就开始走）。
显然，时钟是假的，只是非常准确的复制品。为了快速卖掉它们，X 想把它们都设置在同一时间（所以时间是否正确并不重要——他可以说这是“制造商的时间”），然后摇晃他的包来制作他们打勾。
为了设置时间，他必须旋转一个上链表冠，使时钟的指针移动：时针比分针慢 60 倍，分针比秒针慢 60 倍。表冠转一圈，秒针转一圈；虽然旋转只需要一秒钟，但将时间更改为 6 小时需要 6 分钟。只允许顺时针旋转表冠以保护时钟的脆弱机制。
帮助程序员 X 尽量减少准备出售时钟的工作量，选择将所有时钟设置为的最佳时间。
输入：
第一行包含一个自然的 n (1 ≤ n ≤ 50000)——时钟的数量。
接下来的 n 行包含每个时钟的时间，格式为“h:mm:ss”，其中 h (1 ≤ h ≤ 12) 表示小时，mm 和 ss (00 ≤ mm,ss ≤ 59) – 分钟和秒。
输出：
所有时钟的时间都需要设置为上述格式。
示例 输入
3
11:30:00
12:10:01
6:10:18输出
12:10:01
#include<iostream>
using namespace std;
struct Clock {
int hours;
int mins;
int secs;
Clock() {
hours = mins = secs = 0;
}
};
void strtotime(string str, Clock& clock) { //converts string input to time
if (str[1] == ':') {
clock.hours = (str[0] - 48);
clock.mins = (str[2] - 48) * 10 + (str[3] - 48);
clock.secs = (str[5] - 48) * 10 + (str[6] - 48);
}
else {
clock.hours = (str[0] - 48) * 10 + (str[1] - 48);
clock.mins = (str[3] - 48) * 10 + (str[4] - 48);
clock.secs = (str[6] - 48) * 10 + (str[7] - 48);
}
}
double calctime(Clock from, Clock to) {//calculates time taken to change one clock time to other's
//calculate time for hours
double minutes;
if (from.hours > to.hours) {
minutes = 12 - (from.hours - to.hours);
}
else {
minutes = to.hours - from.hours;
}
//calculate time for mins
double seconds;
if (from.mins > to.mins) {
seconds = 60 - (from.mins - to.mins);
}
else {
seconds = to.mins - from.mins;
}
//calculate time for secs
double seconds2;
if (from.secs > to.secs) {
seconds2 = 60 - (from.secs - to.secs);
}
else {
seconds2 = to.secs - from.secs;
}
double totalTime = minutes * 60 + seconds + (seconds2 / 60);
return totalTime;
}
int main() {
int n;
string str;
cin >> n;
Clock* clock = new Clock[n];
for (int x = 0; x < n; x++) {
cin >> str;
strtotime(str, clock[x]);
}
double totaltime;
double mintime;
int loc = 0;
bool first = true;
double* timearr = new double[n];
for (int x = 0; x < n; x++) {
totaltime = 0.0;
for (int y = 0; y < n; y++) {
if (x != y) {
totaltime += calctime(clock[y], clock[x]);
}
}
if (first) {
mintime = totaltime;
first = false;
}
else {
if (totaltime < mintime) {
mintime = totaltime;
loc = x;
}
}
}
cout << clock[loc].hours;
cout << ':';
if (clock[loc].mins < 10) {
cout << 0 << clock[loc].mins;
}
else {
cout << clock[loc].mins;
}
cout << ':';
if (clock[loc].secs < 10) {
cout << 0 << clock[loc].secs;
}
else {
cout << clock[loc].secs;
}
}