APCS 110/01 實作題第三題題解切割費用

2021-01-09 17:00:42 by Akira

題目敘述

有個長度 \(L\) 的棍子被切了 \(N\) 次，把一段棍子切下去一份為二的花費為該段棍子切割前的長度。

給你 \(N\) 次切割的切割點位置，請計算總花費。

輸入格式

\[
\begin{matrix}
N & L \\
x_1 & p_1 \\
x_2 & p_2 \\
... \\
x_N & p_N
\end{matrix}
\]

\(N \le 200000, L \le 10000000\)

\(0 < x_i < L\) ; 所有的 \(x\) 皆相異

\(1 \le p_i \le N\) 代表 \(x_i\) 是第幾次的切割點 ; 所有 \(p_i\) 皆相異

保證答案不超過 \(2^{60}\)

輸出格式

印出一個數字：總花費

範例輸入

2 10
3 2
9 1

範例輸出

題解

C++ 參考解答

可以使用 STL 的 std::set 儲存並快速找到鄰近切割點

#include <cstdio>
#include <algorithm>
#include <set>

const int NMAX = 200000;

int X[NMAX];

int main() {
  int N, L;
  scanf("%d%d", &N, &L);
  for (int i = 0; i < N; i++) {
    int x, p;
    scanf("%d%d", &x, &p);
    X[p - 1] = x;
  }
  long long ans = 0;
  std::set<int> s {0, L};
  for (int i = 0; i < N; i++) {
    auto it = s.insert(X[i]).first;
    ans += *next(it) - *prev(it);
  }
  printf("%lld\n", ans);
  return 0;
}

[題解] [APCS] [APCS 110/01]

APCS 110/01 實作題第三題題解 切割費用