2019 ICPC World Finals Problem J. Miniature Golf

Solution

設$l$為$l_0$時$i$的總分為$s_{i,l_0}$，$s_{i,l_0}={\sum }_{k}min(a_{i,k},l_0)$，讓$l$從小到大依次變化，可以發現$s_{i,l}$表現為一個斜率非負的上凸殼（上凸殼的左邊一半），${\Delta }_l=s_{i,l+1}?s_{i,l}={\sum }_k[a_{i,k}>l]$，且至多有$h+1$條斜率不同的線段。

當兩個凸殼$i,j$交于一點，且該點所處的兩條線段斜率不同時，$i,j$之間的排名關系會發生變化，顯而易見的是，兩個$h+1$段上凸殼能找到$O(h)$個上述交點，因此我們只需要求出每個$i,j$交點和交點處$i,j$的排名變化，即可算出任意時刻某點排名。

具體的，我們把$a_{i,1},a_{i,2}...a_{i,h}$排序，然后對于每個$i,j$，求出$a_i,a_j$中的所有不同的值$b_1,b_2,b_3...b_n$，且令$b_0=0,b_{n+1}=10^9$，顯然$(b_k,b_{k+1}]$這一段中的上述交點唯一，直接計算即可，時間復雜度為$O(p^{2}h)$。

最后把所有$O(p^{2}h)$個排名變化按時間排序統計最小值即可。
總時間復雜度$O(p^{2}hlogph)$。

Code

#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=20005; 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; } PR V[505][50005]; int a[505][55],b[50005],Num[505],num; void add(int x) { if (b[num]==x) return; b[++num]=x; } signed main() {int n=read(),m=read();for (int i=1;i<=n;i++){for (int j=1;j<=m;j++) a[i][j]=read();sort(a[i]+1,a[i]+m+1);}for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++){int nw=1; b[num=1]=0;for (int k=1;k<=m;k++){while (nw<=m&&a[j][nw]<=a[i][k]) add(a[j][nw]),nw++;add(a[i][k]);}while (nw<=m) add(a[j][nw]),nw++;add(1000000000);ll x1=0,x2=0,s1=0,s2=0;for (int k=1;k<num;k++){while (x1<m&&a[i][x1+1]<=b[k]) x1++;while (x2<m&&a[j][x2+1]<=b[k]) x2++;if (x1>x2&&s1>=s2){ll t=(s1-s2-1)/(x1-x2)+1,p=(s1-s2)/(x1-x2)+1;if (p+b[k]<=b[k+1]) V[i][Num[i]++]=MP(b[k]+p,-1);if (s1!=s2&&t+b[k]<=b[k+1]) V[j][Num[j]++]=MP(b[k]+t,1);}else if (x1<x2&&s1<=s2){ll t=(s2-s1-1)/(x2-x1)+1,p=(s2-s1)/(x2-x1)+1;if (p+b[k]<=b[k+1]) V[j][Num[j]++]=MP(b[k]+p,-1);if (s1!=s2&&t+b[k]<=b[k+1]) V[i][Num[i]++]=MP(b[k]+t,1);}s1+=(m-x1)*(b[k+1]-b[k]),s2+=(m-x2)*(b[k+1]-b[k]);}}for (int i=1;i<=n;i++){sort(V[i],V[i]+Num[i]);int mn=n,nw=n;for (int j=0;j<Num[i];j++){nw+=V[i][j].se;if (V[i][j].fi!=V[i][j+1].fi) upmin(mn,nw);}printf("%d\n",mn);}return 0; }

總結

以上是生活随笔為你收集整理的2019 ICPC World Finals Problem J. Miniature Golf的全部內容，希望文章能夠幫你解決所遇到的問題。

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