ZeroJudge F607: 切割費用

有一根長度為 L 的棍子，你會把這個棍子切割 N 次。

假設一開始棍子左端放在數線上 0 的位置，棍子的右端放在數線上 L 的位置，每次的切割會給定一個介於 0 到 L 的數字表示要切個的位置，你要把穿過個這位置的棍子切成兩段，而所需的花費就等於所切割的棍子的長度。

範例測資

範例輸入範例輸出
第一行有兩個整數 N 和 L。接下來 N 行每行有兩個整數 X 和 i，表示 X 位置被切過一刀，而這刀是全部的切割中的第 i 刀，保證 i 是介於 [1, N] 的整數且不會重複。輸出一個整數表示總共的切割費用，答案可能超過 231，但不會超過 260。
3 7
2 2
3 1
5 3		14

解題思路

使用二分搜的方式來確認要下刀的地方是在哪一個區段，使用一個陣列將每一次下刀的位置存起來，包括最一開始的頭與尾。下刀的費用就是下刀的那個位置的線段長度。

範例程式碼－ZeroJudge F607: 切割費用

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, L;
    cin >> N >> L;
    map<int, int>MAP;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        MAP[b] = a;
    }
    vector<int> line;
    line.push_back(0);
    line.push_back(L);
    long long int ans = 0;
    for (auto it:MAP) {
        const int knife = it.second;
        int L = 0, R = line.size();
        while (L <= R) {
            const int middle = (L + R) / 2;
            if (knife > line[middle]) L = middle + 1;
            else R = middle - 1;
        }
        const long long int len = line[L] - line[R];
        ans += len;
        line.insert(line.begin()+L, knife);
    }
    cout << ans << "\n";
}

//ZeroJudge F607
//Dr. SeanXD
標籤

相關文章

發佈留言