18448 Best Subsequence

길이 $N$의 수열 $w_i$가 주어집니다.

적절한 인덱스를 골라
$1\leq i_1 \leq i_2 \leq i_3 \dots \leq i_k \leq N$
$max( ( w_{i_1} + w_{i_2} ) , ( w_{i_2} + w_{i_3} ) \dots , ( w_{i_K} + w_{i_1} ) )$

를 최소화시키면 됩니다.

 

 

 

 

---

 

 

 

$max(a, b, c)$와 같은 형태이므로 파라메트릭을 사용합시다. 상한을 $x$로 정했다고 생각합시다. 여기서 그리디하게 접근해봅시다. 이때 길이 $K$ 이상의 수열을 구성할 수 있으면 됩니다.

가장 작은 원소는 무조건 먹는 것이 이득일 것입니다.

그 다음 작은 원소도 무조건 먹는 것이 이득입니다.

세 번째 작은 원소는? 현재 수열에

$w_1 \dots w_3 \dots w_2$

이런 느낌으로 있을 것입니다. 만약 $w_3$을 안 먹는다면, $w_1$과 $w_2$ 사이의 공간에서는 아무것도 안 먹어야 합니다. 아니면 그 원소를 $w_3$로 바꿔치기해도 문제가 없기 때문입니다. 어차피 안 먹는거보단 먹는게 이득이니, 3번째 작은 원소도 먹는 것이 이득입니다. 물론 양 옆과 비교해서 합이 상한을 넘으면 먹으면 안됩니다.

최종 선택된 개수가 $K$이상이면 가능합니다.

 

$set$을 이용해 구현하면 $O(NlogNlog2e9)$에 풀 수 있습니다.