旅行家问题2

显然，身为旅行家，爬山是他不能回避的问题。地图上存在 $N$ 座高度 $h_i$ ，由于这些山实在是太高惹，他们的宽度和彼此之间的距离都可以忽略不计。每座山的山顶存在一个高为 $x_i$ 的梯子，

他可以通过这个梯子到达高度可及的山顶，通俗的来说从高山i的山顶，可以转移到 $h_j \leq h_i+x_i$ 的高山j的山顶上去，同时交付 $x_i$ 的梯子使用费。

如果他想达到当前山顶的梯子高度所不能及的高山，他便需要搭乘飞机并交纳 $h_j-h_i$ 的运输费。

旅行家从一号山出发，他需要访问所有高山并返回一号山，请你帮他设计一个路线，使他花费的费用最小。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ pair <int, int> a[100010]; int n; ll ans = 0; cin >> n; for (int i = 0; i < n; i++) cin>>a[i].first>>a[i].second, ans += a[i].second; sort(a, a + n); int h = a[0].first + a[0].second; for (int i = 1; i < n; i++) { if (a[i].first > h) ans += a[i].first - h; h = max(h, a[i].first + a[i].second); } printf("%lld\n", ans); return 0; }

详情