P3819 松江 1843 路讲解

zrl123456 · 2024-01-06 12:35:30 · 题解

这道题我会讲解很多种思路。

30 分做法：

暴力枚举这条路的每个点，取最小值。
时间复杂度为 O(nt)

70 分做法：

通过分析，我们发现只需要考虑这 n 个房子即可。~~（样例是迷惑你的）~~
为什么呢？
因为若左边的人数比右边多，按照少数服从多数的原则，应往左找左边那个点，右边也一样。
若两边人数相同，则在左边那个点到右边那个点这个区间代价是一样的。
时间复杂度为 O(n^2)。

100 分做法 1：

我们用前缀和和后缀和来维护，设 sum_i 为这个点左边的人走到这个点的代价，summ_i 是右边的代价。
最后枚举每个点即可。
时间复杂度为 O(n)。
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll n,l,x[100005],r[100005],sum[100005],summ[100005],num,numm,minn=INF;
int main(){
    cin>>l>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>r[i];
    for(int i=2;i<=n;i++){
        num+=r[i-1];
        sum[i]=sum[i-1]+(x[i]-x[i-1])*num;
    }
    for(int i=n-1;i;i--){
        numm+=r[i+1];
        summ[i]=summ[i+1]+(x[i+1]-x[i])*numm;
    }
    for(int i=1;i<=n;i++) minn=min(minn,sum[i]+summ[i]);
    cout<<minn;
    return 0;
}

100 分做法 2：

此做法是 70 分做法的强剪枝，若左边的人数加上这栋房子的人数还没右边多，就不需要费时间算了。
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,l,x[100005],r[100005],sum[100005],minn=0x3f3f3f3f3f3f3f3f;
int main(){
    cin>>l>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>r[i];
        sum[i]=sum[i-1]+r[i];
    }
    for(int i=1;i<=n;i++){
        if(sum[i]>=sum[n]-sum[i]&&sum[i-1]<=sum[n]-sum[i-1]){
            ll sum=0;
            for(int j=1;j<=n;j++){
                sum+=r[j]*abs(x[i]-x[j]);
            }
            minn=min(minn,sum);
        }
    }
    cout<<minn;
    return 0;
}

最优解：

这就是题解里大佬的思路了，我用快读快写优化了一下，实际就是将上述满分做法 1 写成了一个循环。

k=min(r[le],r[ri]);
r[le]-=k;
r[ri]-=k;

这一段表示左右两边有 k 个人已经转移完成。

ans+=k*(x[ri]-x[le]);

这是累加答案，(x_{ri}-x_{le}) 实际就是双方向中间走的路程和。

if(!r[le]) ++le;
if(!r[ri]) --ri;

这是左右端点转移。
最终代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,l,x[100005],r[100005],ans,le=1,ri,k;
long long read(){
    long long f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
void write(long long x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>=10){
        write(x/10);
    }
    putchar(x%10^48);
}
int main(){
    l=read();
    ri=n=read();
    for(int i=1;i<=n;++i){
        x[i]=read();
        r[i]=read();
    }
    while(le<ri){
        k=min(r[le],r[ri]);
        r[le]-=k;
        r[ri]-=k;
        ans+=k*(x[ri]-x[le]);
        if(!r[le]) ++le;
        if(!r[ri]) --ri;
    }
    write(ans);
    return 0;
} //44ms 最优解

P3819 松江 1843 路 讲解