题解：P10607 物理实验 (hard)

yywlp · 2024-06-19 17:12:35 · 题解

简单题，有上一问的基础非常容易。

这里每个要条件需要达成最少 k_i 次，似乎不能直接简单往回走了，这里还需要回头再回头，有点懵。

但是参考一下上一题：走到最后再往回。那这个是不是每次都走到最前面再往后呢？没错！我们开个结构体将条件按 y_i 排序，对于第一个条件会发现，这个条件需要在 \le y_i 的某个位置转 k_i-1 次，那我肯定每次都走到最前面再转更好，反正这 k_i-1 次无论如何都是要转的，如果在后面提前转了肯定会亏。而对于 x_i 最大的条件就如同上一题，肯定是走到最后再一起转，所以我们再开个结构体把条件按 x_i 排序。

前一个从前往后扫维护最前面的 y_i，后一个从后往前扫维护最后面的 x_i，然后再记 k 表示重复了几次，满足当前条件的 k_i 就往后或往前调扫描线，每次看当前应该还要重复几次，乘上前缀最小值 + 后缀最小值就行。

记得开 long long，因为这个 WA 了好几次QAQ。

时间复杂度在排序 \mathcal O(m\log m+n)。

Code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int M=2e5+10;
int n,m;
int a[M],mnh[M],mnq[M];
struct NODE{
    int x,y,k,id;
}n1[M],n2[M];
bool cmpx(const NODE&A,const NODE&B){
    if(A.x==B.x)return A.y<B.y;
    return A.x<B.x;
}
bool cmpy(const NODE&A,const NODE&B){
    if(A.y==B.y)return A.k>B.k;
    return A.y<B.y;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&n1[i].x,&n1[i].y,&n1[i].k),n2[i]=n1[i],n1[i].id=n2[i].id=i;
    sort(n1+1,n1+m+1,cmpx);
    sort(n2+1,n2+m+1,cmpy);
    mnh[n]=a[n];
    for(int i=n-1;i>=1;i--)mnh[i]=min(mnh[i+1],a[i]);
    mnq[1]=a[1];
    for(int i=2;i<=n;i++)mnq[i]=min(mnq[i-1],a[i]);
    int l=1,r=m,k=0;
    LL ans=0;
    while(r>=1){
        int nr=n1[r].k-k,nl=n2[l].k-k;
        int nk=min(nl,nr);
        ans+=1ll*nk*mnh[n1[r].x]+1ll*nk*mnq[n2[l].y];
        k+=nk;
        while(n1[r].k<=k&&r>=1)r--;
        while(n2[l].k<=k&&l<=m)l++;
    }
    ans-=mnq[n2[1].y];
    cout<<ans<<endl;
    return 0;
}