BOJ 12003 - Diamond Collector (전처리)

https://www.acmicpc.net/problem/12003

유사코엔 전처리문제가 많이나온다

 

<문제설명>

보석의 크기가 최대 5e4개 주어진다. 이 보석들을 두 개의 케이스에 나눠 담고 싶은데, 같은 케이스에 있는 보석의 크기 차이가 최대 K가 되도록 나누고 싶다. 최대한 보석을 전시한다면 몇개를 전시할 수 있을까?

 

<풀이>

p[i] :  보석들중 크기가 a[i]~a[i]+k인 것들의 개수

pmx[i] = i~n-1번 보석 중 p[i]값의 최대

 

i번 보석을을 1번 케이스에 넣을 때 최대 전시 보석 수 = p[i] + pmx[i+p[i]]

 

#include <iostream>
#include <algorithm>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
const int MAX = 5e4;
int main() {
	FAST;
    int n, k, a[MAX], p[MAX], pmx[MAX],mx=0;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);

	for (int i = 0; i < n; i++) 
		p[i] = upper_bound(a, a + n, a[i] + k) - (a + i);

	pmx[n] = 0;
	for (int i = n - 1; i >= 0; i--)
		pmx[i] = max(pmx[i + 1], p[i]);
	
	for (int i = 0; i+p[i] < n; i++) 
		mx = max(mx, p[i] + pmx[i + p[i]]);
	
	cout << mx << '\n';
}