#include <iostream>
#include <stdio.h>
//#define MAX_N (int)1e5
//#define MAX_K (int)1e9
#define MAX_N 7
#define MAX_K 7
//HACK inline 보다 매크로를 사용하는 것이 더 빠르다
#define MIN(a,b) (a) < (b) ? (a) : (b)
#define MAX(a,b) (a) > (b) ? (a) : (b)
#define ABSDIFF(a,b) ( ( a ) > ( b ) ) ? ( ( a ) - ( b ) ) : ( ( b ) - ( a ) )
int answer, N, K;
int A[MAX_N];
int validA[MAX_N];
//HACK 이분탐색을 통해 최적값을 찾아갈 수 있음. 1강 1번과 같은 방법으로 푸는 문제였음
int isValid(int gap)
{
validA[0] = A[0];
for (int i = 1; i < N; i++)
{
validA[i] = MIN(A[i], validA[i - 1] + gap);
}
for (int i = N - 2; 0 <= i; i--)
{
validA[i] = MIN(validA[i], validA[i + 1] + gap);
}
int totalGap = 0;
for (int i = 0; i < N; i++)
{
totalGap += A[i] - validA[i];
if (totalGap > K)
return 0;
}
return 1;
}
int main(int argc, char** argv)
{
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);
for (int case_num = 1; case_num <= T; case_num++)
{
answer = 0;
scanf("%d %d", &N, &K);
for (int i = 0; i < N; i++)
{
scanf("%d", &A[i]);
}
int minGap = 0;
int maxGap = 0;
//HACK maxGap을 O(N) 알고리즘을 통해서 줄일수 있는 만큼 줄인다
for (int i = 0; i < N - 1; i++)
{
maxGap = MAX(maxGap, ABSDIFF(A[i], A[i + 1]));
}
while (minGap < maxGap)
{
int midGap = (minGap + maxGap) / 2;
if (isValid(midGap))
{
maxGap = midGap;
}
else
{
minGap = midGap + 1;
}
}
answer = minGap;
printf("#%d %d\n", case_num, answer);
}
return 0;
}
댓글