题解：P3256 [JLOI2013] 赛车

chrispang · 2026-08-11 07:22:52 · 题解

博客食用更佳。

每一辆车其实就相当于一个一次函数：v_i\cdot t+k_i。我们要做的就是维护全局的上凸包。

对每一个函数按斜率从小到大排序，对于当前元素 i，设 i 追上 j 的时间为 T_1，若：

• 当前栈的大小为 1：若 k_i>k_j，说明 i 一开始速度与所处位置都优于 j，那么 j 一定不能为答案做贡献，就推出栈
• 当前栈的大小大于 1：设栈倒数第二个元素为 p，设 j 追上 p 的时间为 T_2。若 T_2>T_1，说明 j 在追上别人前已经被别人追上了，那么 j 一定不能为答案做贡献，就推出栈

之后这样维护整个栈，最后的栈中元素就是答案。

注意 t=0 比赛还没开始，注意去重。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e4 + 10;

struct Car { ll k, v, id; } a[N];

struct Line { ll k, v; int l, r; } line[N];

int n, m, top, ans_cnt;
int st[N], ans[N];

bool cmp_le(ll num1, ll den1, ll num2, ll den2) { return (__int128)num1 * den2 < (__int128)num2 * den1; }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i].k;
    for (int i = 1; i <= n; i++) cin >> a[i].v;
    for (int i = 1; i <= n; i++) a[i].id = i;

    sort(a + 1, a + n + 1, [](const Car &x, const Car &y) {
        if (x.v != y.v) return x.v < y.v;
        return x.k < y.k;
    });

    for (int i = 1; i <= n; ) {
        int j = i;
        while (j <= n && a[j].v == a[i].v)
            j++;

        int k_start = j - 1;
        while (k_start - 1 >= i && a[k_start - 1].k == a[j - 1].k)
            k_start--;

        line[++m].v = a[i].v;
        line[m].k = a[j - 1].k;
        line[m].l = k_start;
        line[m].r = j - 1;

        i = j;
    }

    for (int i = 1; i <= m; i++) {
        while (top > 0) {
            Line cur = line[i];
            Line t1 = line[st[top]];

            ll num_new = t1.k - cur.k;
            ll den_new = cur.v - t1.v;

            if (top == 1) {
                if (num_new < 0) // t_new < 0，说明 t1 在 t=0 时起跑线就低于 cur
                    top--;
                else
                    break;

            } else {
                Line t2 = line[st[top - 1]];
                ll num_old = t2.k - t1.k;
                ll den_old = t1.v - t2.v;

                if (cmp_le(num_new, den_new, num_old, den_old))
                    top--;
                else
                    break;
            }
        }
        st[++top] = i;
    }

    for (int i = 1; i <= top; i++) {
        int idx = st[i];
        for (int j = line[idx].l; j <= line[idx].r; j++)
            ans[++ans_cnt] = a[j].id;
    }

    sort(ans + 1, ans + ans_cnt + 1);

    cout << ans_cnt << "\n";
    for (int i = 1; i <= ans_cnt; i++)
        cout << ans[i] << " ";

    cout << "\n";

    return 0;
}

:::