题目

题目传送门

题目大意
大家在数轴上生活,公司在s
班车送所有人回家,有n个住处,第i个位置在Xi,居住了Pi的⼈。保证Xi互不相同且均不为s
⼤家⼀起投票向前还是向后,如果票数相同就固定向数轴负方向。
每个⼈是自私的,希望自己尽早回家。(但是注意,虽然是自私的,并不⼀定投自己家的⽅向)
到家了必须下车。(因为自私)
问⼤家都做最优决策的情况下,最后⼀个回家的⼈需要多久到家?(车速为1)

(from wwwwodddd orz)

题解

考虑某个时刻最左端的是a个人的家l,最右端是b个人的家r,设a>=b
那么最终一定是先到最左端再到最右端,所以这(a+b)个人一定都希望尽快到l,那么他们的选择是一样的(到l之前)。
于是我们可以把ab合并,即将r删去,l改为有(a+b)个人,并加上权值(r-l)。
注意这里的权值意义为走到l后去r的代价(显然此时可以一路直行),所以若上一次删的和这一次删的是同方向的,权值不用累加(否则会造成重复,只要计算最远的即可)。
a<b也同理,如此一直操作,知道公司左侧or右侧无人选择,那么一路直行到有人的那侧的最边上再加上那个点的权值就做完啦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//AGC023d_Go Home
//要发现最左端和最右端可以合并的性质;因为人数没开long long而WA了一次
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int x; long long num;
}a[100005];
long long ans,dis[100005];
inline int read()
{
char ch=getchar(); int ans=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch<='9'&&ch>='0') ans=ans*10+ch-48,ch=getchar();
return ans;
}
bool cmp(node t1,node t2){return t1.x<t2.x;}
int main()
{
int n=read(),s=read();
for (int i=1; i<=n; i++) a[i].x=read(),a[i].num=read();
sort(a+1,a+1+n,cmp);
int l=1,r=n,t=2;
while (a[l].x<s&&a[r].x>s)
if (a[l].num<a[r].num) a[r].num+=a[l].num,dis[r]+=dis[l]+((t!=0)?(a[r].x-a[l].x):0),t=0,l++;
else a[l].num+=a[r].num,dis[l]+=dis[r]+((t!=1)?(a[r].x-a[l].x):0),t=1,r--;
if (a[l].x>s) ans=dis[r]+a[r].x-s;
else ans=dis[l]+s-a[l].x;
printf("%lld\n",ans);
return 0;
}

回家…w…回来了呢
大概 是巧合也不是巧合吧