题解：P10607 物理实验 (hard)

__AKcepted · 2026-08-09 16:31:49 · 题解

题意解释

给你一个数轴与一个小球，数轴上每个点有一个 a_i 表示小球从这里转向的代价。要求小球从 x_i 滚到 y_i 滚 k_i 次，求最小代价。

思路分析

贪心。
考虑到想让花费尽可能小，就尽可能少转向。那不难发现，我们可以走到最右边再左转，走到最左边再右转。这样途经的点我们下次就可以少走一个来回了。
如果我们把最远点走到要求了的次数，那途经的点中：

• 次数小于等于其，不管了。
• 次数大于其，记下来下次再走。

这就是大体思路。 所以不难想到我们需要维护一个区间最大值，我直接大炮打蚊子使用 ST 表。不懂左转。
直接见代码。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5;
struct node{
    int r,l,k;
}a[N];
int n,m,ans,l,r; 
int v[N],f[N][55];
bool cmp1(node x,node y)
{
    if(x.r!=y.r) return x.r>y.r;
    return x.k>y.k;
}
bool cmp2(node x,node y)
{
    if(x.l!=y.l) return x.l<y.l;
    return x.k>y.k;
}
int find_min(int l,int r)
{
    int k=log2(r-l+1);
    return min(f[l][k],f[r-((1<<k)-1)][k]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i],f[i][0]=v[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=m;i++) cin>>a[i].r>>a[i].l>>a[i].k;
    sort(a+1,a+m+1,cmp1);
    for(int i=1;i<=m;i++)
    {
        int need=a[i].k-r;
        if(need<=0) continue;
        ans+=need*find_min(a[i].r,n);
        r=a[i].k;
    }
    sort(a+1,a+m+1,cmp2);
    for(int i=1;i<=m;i++)
    {
        int need=(a[i].k-1)-l;
        if(need<=0) continue;
        ans+=need*find_min(1,a[i].l);
        l=a[i].k-1;
    }
    cout<<ans;
    return 0;
}

结束！