题解 P3819 【松江1843路】

_Lemon_ · 2017-07-04 21:33:12 · 题解

本题乍一看毫无头绪，但只要在纸上手算一下样例就能发现本题的关键，其实就是模拟

首先设本题答案为ans

我们知道，车站一定是修在第一间房子和最后一间房子之间。

所以ans至少是 第一间房子和最后一间人数最小值 乘以 两间房子的距离。

然后将人数少的那间清空，指针更新，人数多的那间减去人数少的。

一直这么运算，直到只剩下一间房屋有人，那公交站肯定是修在他家门口啦。

#include<bits/stdc++.h>
using namespace std;
long long s[100001],people[100001];
int main()
{
    long long n,l,k,i,end,tou;//end指当前的最后一间房屋，tou只当前第一间房屋。
    long long ans=0;
    cin>>l>>n;
    for(i=1;i<=n;i++)
      cin>>s[i]>>people[i];
    end=n;
    tou=1;
    while(end>tou)
    {
        k=min(people[tou],people[end]);
        people[tou]-=k;
        people[end]-=k;
        ans+=k*(s[end]-s[tou]);
        if(people[end]==0) end--;
        if(people[tou]==0) tou++;//如果房间被清空，则指针变动.
    }
    cout<<ans;
    return 0;
}