LUOGU P3819 松江1843路

传送门

解题思路

比较有意思的一道思路题，首先假如有两个点，每个点的人数都是1，那么将车站建在两个点之间的任意一个位置最后的答案均为这两点的长度，那么考虑在加一个人数为1的点在这两个之间，那么最优的一定是在这个点建在新加的点上，这样的长度还是原来两点的长度，然后做法就被这样yy出来了。每次将最左端和最右端的点的距离假如答案，因为最优一定是在他们两个中间，而这样这两个点的贡献就是距离，所以用两个指针扫即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
const int MAXN=100005;
typedef long long LL;

inline LL rd(){
    LL x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

LL n;
LL ans,l,x[MAXN]; 
int r[MAXN];

int main(){
    l=rd(),n=rd();
    for(register int i=1;i<=n;i++)
        x[i]=rd(),r[i]=rd();
    int L=1,R=n;
    while(L<R){
        int now=min(r[L],r[R]);
        ans+=(x[R]-x[L])*now;
        r[L]-=now,r[R]-=now;
        if(r[L]==0) L++;
        if(r[R]==0) R--;
    }
    cout<<ans<<endl;
    return 0;
}