背景

附中机房谁最虚? 高二一班***! 感觉很顺, 是吧?

题目描述

今天, 丧尸 czy 开着挖掘机去上学 (……). 但是他发现他的 mz 满天下, 所以一路上他碰到了好 多他的 mz. 一开始他以 1km/min 的速度 (=60km/h……) 开着挖掘机前进. 他发现他只会在恰好到 达某一时刻或者到达某个距离遇到 mz. 每次遇到 mz, czy 都会毫不犹豫的把她们顺路捎走. 但是他实在是太虚了, 以至于当有 i 个 mz 时他的速度下降到 1/ (i+1). 具体说, 一开始 czy 以 1km/min 速度前进, 有 1 个 mz 的时候速度变为 1/2 km/min, 有 2 个时变为 1/3 km/min……以此类推. 现在问题来了, 给出每个 mz 在何时出现, 请你算出 czy 到学校要多久.

格式

输入第一行 2 个数 n, m, 分别表示 mz 数和 czy 与学校的距离 (km)

接下来 2 到 n+1 行由字符串与数字构成:

Dist x 表示在距离达到 x km 时出现一个 mz

Time x 表示在时间达到 x min 时出现一个 mz

输出一个整数, 表示到达学校的时间. 如果不能整除, 直接输出整数部分即可.

样例输入

2 20
Time 3
Dist 10

样例输出

47

数据范围

对于 30% 数据,\(n, m \leq 50\)

对于 50% 数据,\(n, m \leq 2000\)

对于 100% 数据,\(n, m \leq 200000\),\(x \leq 10^9\), 保证输入的数字都是整数

Explanation

需要一点优化 (map, set, priority_queue, sort 皆可). 然后简单模拟.

话说又看了看 @xmcp 的代码 233

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#define $ if(0)

using namespace std;
typedef long long lli;
typedef long double llf;

class SmallerPriorityQueue
{
public:
    priority_queue<lli> pq;
    void push(lli v) { this->pq.push(-v); }
    lli top(void) { return -this->pq.top(); }
    void pop(void) { this->pq.pop(); }
    lli get(void) { lli res = this->top(); this->pop(); return res; }
    bool empty(void) { return this->pq.empty(); }
};

SmallerPriorityQueue qdist, qtime;
// priority_queue<long long, vector<long long>, greater<int> > qdist, qtime;

int n; lli m;
char str[32];

int main(int argc, char** argv)
{
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        lli a; scanf("%s%lld", str, &a);
        if (str[0] == 'D')
            qdist.push(a);
        else if (str[0] == 'T')
            qtime.push(a);
        else
            throw ;
    }
    // Done reading, emulating excavator movement
    llf c_tim = 0.0, // Elapsed time, also the result
        c_vel = 1.0, // The velocity, powered by (-1) / a.k.a. the multiplicative reverse
        c_dis = 0.0; // Elapsed length
    // while (!qdist.empty() || !qtime.empty()) {
    while (c_dis + 1e-5 < m) {
        llf sel_a = qtime.empty() ? 1e100 : (qtime.top() - c_tim);
        llf sel_b = qdist.empty() ? 1e100 : (qdist.top() - c_dis) * c_vel;
        if (sel_a >= 1e100 && sel_b >= 1e100) {
            c_tim += (m - c_dis) * c_vel;
            break;
        }
        if (sel_a < sel_b) {
            c_dis += (qtime.top() - c_tim) / c_vel;
            c_tim = qtime.top();
            qtime.pop();
        } else {
            c_tim += (qdist.top() - c_dis) * c_vel;
            c_dis = qdist.top();
            qdist.pop();
        }
        c_vel += 1.0;
        /*
        int select = 0; // 0 -> none, 1 -> dist, 2 -> time
        lli selval = 0; // Selected value
        if (qtime.empty()) {
            select = 1;
            selval = qdist.get();
        } else if (qdist.empty()) {
            select = 2;
            selval = qtime.get();
        } else { // No empty range
            lli a = qdist.top(), b = qtime.top();
            llf a_tim = ((llf)a - c_dis) / (1.0 / c_vel),
                b_tim = (llf)b - c_tim;
            if (b < a_tim) { // Reach b first
                select = 2;
                selval = qtime.get();
            } else {
                select = 1;
                selval = qdist.get();
            }
        }
        $ printf("selecting %d with %lld;\n", select, selval);
        // Done selecting appropriate maze.
        // Retrieving distance.
        if (select == 1) {
            llf d_dist = (llf)selval - c_dis,
                d_time = d_dist * c_vel;
            if (c_dis + d_dist > (llf)m)
                break;
            $ printf("mig cur %Lf %Lf %Lf add %Lf %Lf\n", c_vel, c_tim, c_dis, d_time, d_dist);
            c_dis = selval;
            c_tim += d_time;
            c_vel += 1.0;
        } else if (select == 2) {
            llf d_time = (llf)selval - c_tim,
                d_dist = d_time * (1.0 / c_vel);
            if (c_dis + d_dist > (llf)m)
                break;
            // $ printf("mig cur %Lf %Lf %Lf add %Lf %Lf\n", c_vel, c_tim, c_dis, d_time, d_dist);
            c_dis += d_dist;
            c_tim = selval;
            c_vel += 1.0;
        }
        */
    }
    // c_tim += ((llf)m - c_dis) / (1.0 / c_vel);
    // c_dis = (llf)n;
    lli res = (lli)c_tim;
    printf("%lld\n", res);
    return 0;
}