AGC023D - Go Home

題目描述

Solution

我們首先把這些人分成在$s$左邊和在$s$右邊兩類，考慮最左邊的一群人$A$和最右邊的一群人$B$，這兩群人中必然有其中一群人是最后到家的。而是否最后到家取決于這兩群人的人數（因為倘若只剩下兩群人，一個要往左，一個要往右，必然會往人多的一個方向去）。

設兩群人的人數分別為$a,b$，且$a<b$。
則$A$的人必然會選擇投票去$B$的方向，因為無論如何它們都會比$B$的這些人慢，反而不如讓$B$盡可能的早到。

于是我們可以合并$A,B$，并加上$A?>B$的貢獻（若與上一次合并的方向相同，就不需要增加這一次的貢獻）。
這樣一直合并最兩邊的人，知道只剩下一邊的人的時候，就能求出答案了。

時間復雜度$O(nlgn)$。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=600005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } ll s[MAXN]; struct anode{ ll x,y; } a[MAXN]; int compare(anode x,anode y){ return x.x<y.x; } int main() {int n=read(),S=read();for (int i=1;i<=n;i++) a[i]=(anode){read(),read()};sort(a+1,a+n+1,compare);int l=1,r=n,flag=-1;while (a[l].x<S&&a[r].x>S){if (a[l].y>=a[r].y) a[l].y+=a[r].y,s[l]+=s[r]+((flag!=1)?(a[r].x-a[l].x):0),flag=1,r--;else a[r].y+=a[l].y,s[r]+=s[l]+((flag!=0)?(a[r].x-a[l].x):0),flag=0,l++;}printf("%lld\n",(a[l].x>S)?s[r]+a[r].x-S:s[l]+S-a[l].x);return 0; }

總結

以上是生活随笔為你收集整理的AGC023D - Go Home的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。