Re[2]: Время черепахи
От: olimp_20  
Дата: 02.07.15 11:44
Оценка:
Здравствуйте, Кодт:

  Новый вариант алгоритма
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n;
    int vmax, d;
    scanf("%d%d%d", &vmax, &d, &n);

    if(n==0)//частный случай
    {
        printf("00:00\n");
        return 0;
    }

        //чтение данных
    vector<int> x(n,0.0);
    vector<int> t(n,0.0);
    int hh, mm;
    for(int i=0; i<n; ++i) {
        scanf("%d %d:%d", &x[i], &hh, &mm);
        t[i]=hh*60+mm;
    }


    int s = x[n-1];//вся дистанция
    for(int i=1; i<n; i++) x[i] -= x[i-1];//ч[i] - дистанция между цветком "і-1" и "і"

        //бинарный поиск 
    int mi(0), ma(t[n-1]);//мин и макс зажержка пеерд стартом черепахи
    int time;//результат
    int cnt(0);//количество съеденных цветов: от начала до последнего цветка

    while(ma!=mi){
        int wait = (ma+mi)/2;
        time = wait; 
        cnt=0;
        for(int i=0; i<n; ++i)
            if(time*vmax+x[i]>=t[i]*vmax){ //time+x[i]/vmax>=t[i] - успел ли вырасти цветок
                ++cnt;
                time += d;
            }
 
        if(time>=t[n-1]) ma = wait;//изменить диапазон бинарного поиска
        else mi = wait+1;
    }

    int iS = ceil(s*1.0/vmax);//время для преодоления расстояния назад
    time += (n-cnt)*d+iS;


    printf("%02d:%02d\n", time/60, time%60);

    return 0;
}

Проблема: чем неправильный такой алгоритм — проходит всего 2 теста и как ускорить его работу?
Отредактировано 02.07.2015 12:03 olimp_20 . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.