[SwExpertAcademy] 평등주의

문제 출처 :

https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4

알고리즘 분석 :

문제 해결에 필요한 사항

1. 파라매트릭 서치

인접한 숫자 차이의 최대값을 최소로 하기위해 파라매트릭 서치를 이용한다.

즉, 정답이 될 것이라고 가정하고 측정 한 후 k번 이하만에 조건을 만족시킨다면 최댓값을 줄여보고 

그게 아니라면 최댓값을 늘려가며 정답을 구할 수 있다.

이때 -> 방향으로도 차이가 mid 이하여야 하고 <- 방향으로도 차이가 mid 이하여야 하기에 

양방향으로 mid 이하로 만들어가며 최대 k번만에 가능한지 확인한다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream>   #define max(a,b)(a > b ? a : b)   int arr[100002]; int tArr[100002];   void _copy(int n) {     for (int i = 0; i < n; i++)         arr[i] = tArr[i]; } int _abs(int a) {     return a > 0 ? a : -a; } int main() {     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {         int n, k;         scanf("%d %d", &n, &k);           for (int i = 0; i < n; i++) {             scanf("%d", &arr[i]);             tArr[i] = arr[i];         }           int s = 0, e = 1e9;         int ans = 0;         while (s < e) {             int m = (s + e) >> 1;             int tk = k;             bool chk = true;             _copy(n);             for (int i = 0; i < n - 1; i++) {                 if (arr[i + 1] - arr[i] >= m) {                     tk -= ((arr[i + 1] - arr[i]) - m);                       arr[i + 1] -= ((arr[i + 1] - arr[i]) - m);                     if (tk < 0) {                         chk = false;                         break;                     }                 }             }                          for (int i = n - 1; i >= 1; i--) {                 if (arr[i - 1] - arr[i] >= m) {                     tk = tk - ((arr[i - 1] - arr[i]) - m);                     arr[i - 1] -= ((arr[i - 1] - arr[i]) - m);                     if (tk < 0) {                         chk = false;                         break;                     }                 }             }               if (!chk) {                 s = m + 1;                 ans = s;             }             else {                 e = m;             }         }         printf("#%d %d\n", tc, ans);     }     return 0; } Colored by Color Scripter

cs