Find the Car

题面翻译

一条笔直的公路上有 $k$ 个标志，已知这条公路的长度 $n$，第 $i$ 个标志位于 $a_{i}$ 点，一辆大巴车从 $0$ 点出发，从一个站点到另一个站点匀速行驶，并在 $b_{i}$ 分钟经过第 $i$ 个标志。现给出 $q$ 个询问，求大巴车经过 $d$ 点的时间（向下取整）。

输入有 $t$ 组，对于每组数据的 $q$ 个询问，输出一行，用空格间隔。

对于 $100\%$ 的数据，$1\le t\le 10^4$，$k\le n\le 10^9$，$1\le k,q\le 10^5$，$1\le a_1<a_2<\ldots<a_k=n$，$1\le b_1<b_2<\ldots<b_k\le 10^9$。

题目描述

Timur is in a car traveling on the number line from point $ 0 $ to point $ n $ . The car starts moving from point $ 0 $ at minute $ 0 $ .

There are $ k+1 $ signs on the line at points $ 0, a_1, a_2, \dots, a_k $ , and Timur knows that the car will arrive there at minutes $ 0, b_1, b_2, \dots, b_k $ , respectively. The sequences $ a $ and $ b $ are strictly increasing with $ a_k = n $ .

Between any two adjacent signs, the car travels with a constant speed. Timur has $ q $ queries: each query will be an integer $ d $ , and Timur wants you to output how many minutes it takes the car to reach point $ d $ , rounded down to the nearest integer.

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains three integers $ n $ , $ k $ , and $ q $ , ( $ k \leq n \leq 10^9 $ ; $ 1 \leq k, q \leq 10^5 $ ) — the final destination, the number of points Timur knows the time for, and the number of queries respectively.

The second line of each test case contains $ k $ integers $ a_i $ ( $ 1 \leq a_i \leq n $ ; $ a_i < a_{i+1} $ for every $ 1 \leq i \leq k-1 $ ; $ a_k = n $ ).

The third line of each test case contains $ k $ integers $ b_i $ ( $ 1 \leq b_i \leq 10^9 $ ; $ b_i < b_{i+1} $ for every $ 1 \leq i \leq k-1 $ ).

Each of the following $ q $ lines contains a single integer $ d $ ( $ 0 \leq d \leq n $ ) — the distance that Timur asks the minutes passed for.

The sum of $ k $ over all test cases doesn’t exceed $ 10^5 $ , and the sum of $ q $ over all test cases doesn’t exceed $ 10^5 $ .

输出格式

For each query, output a single integer — the number of minutes passed until the car reaches the point $ d $ , rounded down.

样例 #1

样例输入 #1

4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5

样例输出 #1

0 6 7 
5 4 2 5 
99999999 
1 5 4

提示

For the first test case, the car goes from point $ 0 $ to point $ 10 $ in $ 10 $ minutes, so the speed is $ 1 $ unit per minute and:

• At point $ 0 $ , the time will be $ 0 $ minutes.
• At point $ 6 $ , the time will be $ 6 $ minutes.
• At point $ 7 $ , the time will be $ 7 $ minutes.

For the second test case, between points $ 0 $ and $ 4 $ , the car travels at a speed of $ 1 $ unit per minute and between $ 4 $ and $ 10 $ with a speed of $ 2 $ units per minute and:

• At point $ 6 $ , the time will be $ 5 $ minutes.
• At point $ 4 $ , the time will be $ 4 $ minutes.
• At point $ 2 $ , the time will be $ 2 $ minutes.
• At point $ 7 $ , the time will be $ 5.5 $ minutes, so the answer is $ 5 $ .

For the fourth test case, the car travels with $ 1.2 $ units per minute, so the answers to the queries are:

• At point $ 2 $ , the time will be $ 1.66\dots $ minutes, so the answer is $ 1 $ .
• At point $ 6 $ , the time will be $ 5 $ minutes.
• At point $ 5 $ , the time will be $ 4.16\dots $ minutes, so the answer is $ 4 $ .

坑点多

pj除数那一部分出问题

const int N = 200010;

int a[N], b[N], c[N];
int n, k, q;
int cheak(int x)
{
    int l = 1, r = k;
    int daan = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (a[mid] <= x)
        {
            daan = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return daan;
}
void solve()
{

    cin >> n >> k >> q;
    for (int i = 1; i <= k; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) cin >> b[i];


    while (q--)
    {
        int x; cin >> x;
        int xb = cheak(x);
        int ans = 0;
        ans += b[xb];
        int yu = x - a[xb];
        double pj = 1.0 * (a[xb + 1] - a[xb]) / (b[xb + 1] - b[xb]);
        int ok = yu / pj;
        ans += ok;
        cout << ans << '\n';
    }
} 

分开除出问题

const int N = 200010;

int a[N], b[N], c[N];
int n, k, q;
int cheak(int x)
{
    int l = 1, r = k;
    int daan = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (a[mid] <= x)
        {
            daan = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return daan;
}
void solve()
{

    cin >> n >> k >> q;
    for (int i = 1; i <= k; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) cin >> b[i];


    while (q--)
    {
        int x; cin >> x;
        int xb = cheak(x);
        int ans = 0;
        ans += b[xb];
        int yu = x - a[xb];
        if (yu != 0)
        {
            double pj =  1.0*(a[xb + 1] - a[xb]) / (b[xb + 1] - b[xb]);
            int ok = 1.0*yu / pj;
            ans += ok;
        }
        cout << ans << '\n';
    }
}

正解

const int N = 200010;

int a[N], b[N], c[N];
int n, k, q;
int cheak(int x)
{
    int l = 1, r = k;
    int daan = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (a[mid] <= x)
        {
            daan = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return daan;
}
void solve()
{

    cin >> n >> k >> q;
    for (int i = 1; i <= k; i++) cin >> a[i];
    for (int i = 1; i <= k; i++) cin >> b[i];


    while (q--)
    {
        int x; cin >> x;
        int xb = cheak(x);
        int ans = 0;
        ans += b[xb];
        int yu = x - a[xb];
        if (yu != 0)
        {
            int pj =  yu * (b[xb + 1] - b[xb]) / (a[xb + 1] - a[xb]);
            ans += pj;
        }
        cout << ans << '\n';
    }
}