题解：P10606 物理实验 (easy)

juruo5e59 · 2024-06-19 18:21:25 · 题解

思路：

题目中说的很花，要走过 m 个 x_i 到 y_i 的路线，根据贪心思想，掉头的次数越小越好，所以只需要从原点向右走足够的距离再返回就能实现代价最小化。

求向右走的最少距离很简单，只需要取 \max_{1 \le i \le m} x_i 就是向右走的最小距离。根据题意，移动不需要花费代价，所以又根据贪心思想，总代价就是在满足题意的最左边的掉头位置到 n 点这个范围内的最小值。换句话说，设 k=\max_{1 \le i \le m} x_i，则最小代价为 \min_{k \le i \le n}a_i。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[200010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    int maxn = -1e9;
    for (int i = 1; i <= m; i ++) {
        int x, y;
        cin >> x >> y;
        maxn = max(x, maxn);
    }
    int ans = 1e9;
    for (int i = maxn; i <= n; i ++)
        ans = min(ans, a[i]);
    cout << ans;
    return 0;
}