-2

我一直在尝试为一个在线裁判系统解决这个问题,它需要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;
    }
    
}
4

1 回答 1

-1
  1. 排序时间
  2. 计算每两个邻居与第一个和最后一个元素之间的差异
  3. 找出最大的差值并去掉(解是这个差值的左邻)
于 2021-01-13T10:48:13.070 回答