R619(Div.2) B. Motarack's Birthday

이분탐색을 통해 값을 찾으려고했는데 계속 실패했다!
한번 생각해보자..
이 문제에서는 인접한 수의 차를 최소로 하고싶고 그때의 k를 구하고싶다
그럴때는..! -1과 인접한 숫자들 중 최소와 최대의 평군이 최적이된다
문제를 풀면서는 생각못했는데 -1 옆에없는 수는 무시하는게 맞다
-1 옆에 있을때만 의미가 있으니까 근처에 있는 수를 찾아서 평균값을 구하고 대체해준다
그리고 n만큼 보면서 가장 큰 diff값을 찾으면 된다! ㅠㅠ

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int SIZE = 1e5+5;
int t,n;
int arr[SIZE];
 
int main(){
   scanf(" %d",&t);
   for(int tc=1;tc<=t;tc++){
      memset(arr,0,sizeof(arr));
      scanf(" %d",&n);
      for(int i=0;i<n;i++) scanf(" %d",&arr[i]);
      
      int minn=1e9,maxn=0;
      for(int i=0;i<n;i++){
         if(arr[i]!=-1) continue;
         int prev=i-1,next=i+1;
         if(0<=prev && arr[prev] != -1) minn=min(minn,arr[prev]),maxn=max(maxn,arr[prev]);
         if(next<n && arr[next] != -1) minn=min(minn,arr[next]),maxn=max(maxn,arr[next]);
      }
      int ans = (minn+maxn)/2;
      for(int i=0;i<n;i++) if(arr[i]==-1) arr[i] = ans;
      int k=0;
      for(int i=0;i<n-1;i++) k =max(k,abs(arr[i]-arr[i+1]));
      printf("%d %d\n",k,ans);
   }
}