Demo entry 6640494

code

   

Submitted by anonymous on Sep 12, 2017 at 06:01
Language: C++. Code size: 2.1 kB.

#include <cassert>
#include <iomanip>
#include <iostream>
#include <vector>

/**
 * 利用二分搜索查找,起点和终点所属的区间,返回区间下界的下标
 */
int find(const std::vector< int > &nums, int target)
{
    if (target == nums[nums.size() - 1]) {
        int id = nums.size() - 2;
        return id < 0 ? 0 : id;
    }
    int l = 0;
    int h = nums.size() - 1;
    int result = 0;
    while (l <= h) {
        int mid = (l + h) / 2;
        if (target == nums[mid]) {
            result = mid;
            break;
        }
        if (target < nums[mid]) {
            if (target > nums[mid - 1]) {
                result = mid - 1;
                result = result < 0 ? 0 : result;
                break;
            } else {
                h = mid - 1;
            }
        }
        if (target > nums[mid]) {
            if (target < nums[mid + 1]) {
                result = mid;
                break;
            } else {
                l = mid + 1;
            }
        }
    }
    return result;
}

int main()
{
    int n;
    std::cin >> n;
    std::vector< int > section(n + 1);
    std::vector< int > speed(n);
    for (int i = 0; i < n; ++i) {
        int s, e, sp;
        std::cin >> s >> e >> sp;
        section[i] = s;
        section[i + 1] = e;
        speed[i] = sp;
    }
    int start, end;
    std::cin >> start >> end;

    // 检查输入的合法性
    assert(end > start && start > section[0] && end < section[n]);

    int sid = find(section, start);
    int eid = find(section, end);

    float time = 0.0;
    if (eid == sid) {
        time = (end - start) / (float) speed[sid];
    } else {
        time += (section[sid + 1] - start) / (float) speed[sid];
        for (int i = sid + 2; i <= eid; ++i) {
            time += (section[i] - section[i - 1]) / (float) speed[i];
        }
        time += (end - section[eid]) / (float) speed[eid];
    }
    // 格式化输出
    std::cout.setf(std::ios::fixed);
    std::cout.precision(2);
    std::cout << time << std::endl;
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).