题解：P9521 [JOISC 2022] 京都观光

考虑

(l,x)\to(r,y)

的路径可以

(l,x)\to (r,x)\to (r,y)

，也可以

(l,x)\to (l,y)\to (r,y)

。

前者的代价是

b_x(r-l)+a_r(y-x)

，后者的代价是

a_l(y-x)+b_y(r-l)

。前者比后者更优需要满足

\dfrac{b_x-b_y}{x-y}<\dfrac{a_r-a_l}{r-l}

可以发现这可以放到两个凸包上求解。单调栈建立对于

a,b

的凸包之后，每次选择斜率写的一边走。由于上述式子可以放到到任意局部，所以这是对的。

其实本质就是对于两个凸包进行闵可夫斯基和。

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int n,m,a[maxn],b[maxn]; ll ans=0;
int sta[maxn],stb[maxn],ta,tb;
bool chk(int x1,int y1,int x2,int y2){ return 1ll*y1*x2<=1ll*y2*x1; }
bool cmpa(int x,int y,int z){ return chk(x-y,a[x]-a[y],y-z,a[y]-a[z]); }
bool cmpb(int x,int y,int z){ return chk(x-y,b[x]-b[y],y-z,b[y]-b[z]); }
bool cmpab(int w,int x,int y,int z){ return chk(w-x,a[w]-a[x],y-z,b[y]-b[z]); }
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sta[ta=1]=1; stb[tb=1]=1;
	for(int i=2;i<=n;i++){
		while(ta>1&&cmpa(i,sta[ta],sta[ta-1])) ta--;
		sta[++ta]=i;
	}
	for(int i=2;i<=m;i++){
		while(tb>1&&cmpb(i,stb[tb],stb[tb-1])) tb--;
		stb[++tb]=i;
	}
	int x=1,y=1;
	while(x<ta||y<tb){
		if(x==ta){
			ans+=1ll*(m-stb[y])*a[sta[x]];
			break;
		}
		if(y==tb){
			ans+=1ll*(n-sta[x])*b[stb[y]];
			break;
		}
		if(cmpab(sta[x+1],sta[x],stb[y+1],stb[y])){
			ans+=1ll*(sta[x+1]-sta[x])*b[stb[y]];
			x++;
		}else{
			ans+=1ll*(stb[y+1]-stb[y])*a[sta[x]];
			y++; 
		}
	}
	cout<<ans;
	return 0;
}

题解：P9521 [JOISC 2022] 京都观光

文章操作

相关推荐

评论

题解：P9521 [JOISC 2022] 京都观光