JOI20 Just Long Neckties

문제

https://oj.uz/problem/view/JOI20_ho_t1

문제 보기 - Just Long Neckties (JOI20_ho_t1) :: oj.uz

길이 $N+1$의 배열 A, 길이 $N$의 배열 B가 주어졌을 때 $1<=i<=N+1$인 모든 $i$에 대하여 A에서의 그 원소를 제거한 후 A의 각 원소를 B의 원소와 매칭시켰을 때 $max(A_j-B_j, 0)$의 최댓값을 최소화해야 한다.

$N<=200000$

풀이

일단 제거 조건을 생각하지 말고 길이 $N$의 배열 A, B만을 최적으로 매칭시키는 방법만 생각해 보자.

Observation 1 : 최적의 매칭은 A와 B를 정렬한 후 순서대로 매칭하는 것이다.

Exchange arguments를 이용하여 $a_1<=a_2$, $b_1<=b_2$일 때 $max(a_1-b_1, a_2-b_2)<=max(a_1-b_2, a_2-b_1)$이 성립함을 보이면 각 배열의 최댓값이 다른 원소랑 매칭되어 있다면 조건을 이용하여 귀납적으로 최댓값끼리 매칭되도록 바꿔줄 수 있다.

$a_1-b_1<=a_2-b_1$, $a_2-b_2<=a_2-b_1$이 성립하기 때문에 위 식은 성립한다.

 

기본적인 아이디어는 파라마트릭과 같이 생각할 수 있다. 파라마트릭을 하면 $A_j-B_j<=k$, 각 $A_j$에 대하여 $A_j-k<=B_j$를 만족하도록 매칭하면 된다. 범위에 단조성이 있으므로, 가장 작은 범위를 포함하는 최대의 $A_j$부터 하나씩 $B_j$의 최댓값과 매칭하는 것이 무조건 최적의 상황이고, 어떠한 $k$에 대해서도 성립하는 전략이기 때문에 위 관찰을 얻을 수 있다.

 

이제 매칭 방법을 찾았기 때문에 하나를 제거하였을 때에 대한 것만 해결해 주면 된다.

이는 A의 앞에서부터 매칭시킨 결과에 대한 누적 최대값, A의 뒤에서부터 매칭시킨 결과에 대한 누적 최댓값을 구하고 합쳐주면 된다.

 

시간 복잡도 : $O(NlogN)$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
 
int N, B[MAXN+10];
pii A[MAXN+10];
int ans[MAXN+10];
 
int P[MAXN+10], Q[MAXN+10];
 
int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N+1; i++) scanf("%d", &A[i].first), A[i].second=i;
	for(int i=1; i<=N; i++) scanf("%d", &B[i]);
 
	sort(A+1, A+N+2);
	sort(B+1, B+N+1);
 
	for(int i=1; i<=N; i++) P[i]=max(P[i-1], A[i].first-B[i]);
	for(int i=N; i>=1; i--) Q[i]=max(Q[i+1], A[i+1].first-B[i]);
 
	for(int i=1; i<=N+1; i++) ans[A[i].second]=max(P[i-1], Q[i]);
	for(int i=1; i<=N+1; i++) printf("%d ", ans[i]);
}