https://www.acmicpc.net/problem/23830
문제요약
- N개의 수가 주어짐(10만, 10만)
- K 미만은 +q
- K + r 초과는 -p
- 로 점수를 부여할때 합이 S 이상이 가능한지? 가장 작은 K는 얼마인지
접근법
- 모두에게 +q를 했는데도 S가 안되면 불가능함
- 정렬 후 투 포인터로 접근
- 미만을 만족하기 위한 가장 작은 값 : A + 1
- 초과를 만족하기 위하 가장 작은 값 : A - r
- 두 값이 답이 될 수 있는 후보들임
- 처음에는 다 p를 뺐다고 치고 슬라이딩 윈도우를 적용함
- k ~ k + r 범위에 걸리는 것들 찾기 : 개념 확립이 어려움
- 오른쪽 지점 : 어떤 k + r 에 대해서 초과가 발생하하기 시작하는 점 == k + r이하인 것들은 다 넘어가면서 +p
- 왼쪽 지점 : k 에 대해서 미만이 발생하기 시작하는 점 == k 미만인 것들 다 넘어가면서 +q
더 쉬운 접근법
- 1부터 10만까지 완전 탐색 가능 : 값의 범위가 작음
newbieski