题解：P11339 [COI 2019] SEGWAY

2024zcy · 2025-02-22 21:09:14 · 题解

无脑模拟。。。

这道题可以说是道水题

废话讲到这里，下面正式开始！！！

首先，先将赛道加速器标记。

再用类似于计数排序的方法模拟

AC code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4 + 10;
int n, m, Read_in_array[MAXN][3], Additional_bonus_speed_array[MAXN], Final_usage_time[MAXN], Bucket_sort_array[MAXN * 50];
bool Accelerator_marking[MAXN];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < 3; j ++ ) cin >> Read_in_array[i][j]; // 读入数据，n个人，3个阶段
    cin >> m;
    for (int x; m --;) cin >> x, Accelerator_marking[x] = true; // 标记加速器
    for (int t = 1; t <= 300; t ++ ) {
        for (int i = 1; i <= n; i ++ ) {
            if (Additional_bonus_speed_array[i]) Final_usage_time[i] ++, Additional_bonus_speed_array[i] -- ; // 如果在加速范围就将所需时间++，剩余额外路程--
            else Final_usage_time[i] += Read_in_array[i][(t - 1) / 100]; // 否则时间正常加
        }
        if (!Accelerator_marking[t]) continue; // 如果没有加速器就跳过
        fill(Bucket_sort_array + 1, Bucket_sort_array + 15001, 0); // 初始化
        for (int i = 1; i <= n; i ++ ) Bucket_sort_array[Final_usage_time[i]] ++;
        for (int i = 2; i <= 15000; i ++ ) Bucket_sort_array[i] += Bucket_sort_array[i - 1]; // 前缀和
        for (int i = 1; i <= n; i ++ )
            if (!Additional_bonus_speed_array[i]) Additional_bonus_speed_array[i] = Bucket_sort_array[Final_usage_time[i] - 1] % 20; // 获得加速器
    }
    for (int i = 1; i <= n; i ++ ) cout << Final_usage_time[i] << "\n"; // 输出
    return 0;
}