2018.07.12 atcoder Go Home（贪心）

传送门

题意简述：大家在数轴上生活，公司在 s。

班车送所有人回家，有 n 个住处，第 i 个位置在 xi，居住了 pi 的人。

保证 xi 互不相同。

大家⼀起投票向前还是向后，如果票数相同就固定向数轴负方向，每个⼈是自私的，希望自己尽早回家。

（但是注意，虽然是自私的，并不⼀定投自己家的方向）

到家了必须下车（因为自私）

问大家都做最优决策的情况下，最后⼀个回家的人需要多久到家？

车速为 1。

this is an easy problem.

事实上，这题我们应该倒着思考，对于最后的两队人：最左边的和最右边的，如果最左边的不比最右边的少，那么无论如何投票，最后都会先走到最左边，再走到最右边。这样的话相当于最右边的人并没有选择权，因此他们应该将票投给左边来使左边的人都尽快回家然后使自己尽快回家。这样的话最右边的人的位置已经不重要了，我们可以直接将最右边的人与最左边的人合并，然后继续判断合并之后最左边的人和最右边的人的关系，直到所有人都位于起点的一侧直接全部接完就行了。

代码如下：

#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
inline ll read(){
    ll ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
ll n,s,ans,x[N],p[N];
int main(){
    n=read(),s=read();
    for(ll i=1;i<=n;++i)x[i]=read(),p[i]=read();
    ll l=1,r=n;
    while(l<=r){
        if(x[l]>=s){ans+=x[r]-s;break;}
        if(x[r]<=s){ans+=s-x[l];break;}
        ans+=x[r]-x[l];
        if(p[l]>=p[r])while(p[l]>=p[r]&&l<r)p[l]+=p[r--];
        else while(p[l]<p[r]&&l<r)p[r]+=p[l++];
    }
    printf("%lld",ans);
    return 0;
}

巴特西

2018.07.12 atcoder Go Home（贪心）

最新文章

热门文章