메모리
시간
8808 KB
264 ms
Code
#include <cstdio>
using namespace std;
int n, m;
long long total = 0;
void get_total(int mid, long long *tree)
{
total = 0;
for (int j = 0; j < n; j++)
{
if (tree[j] > mid)
total += tree[j] - mid;
}
}
int main()
{
int mid, max, min;
int val = 1;
scanf("%d%d",&n,&m);
long long tree[n];
for (int i = 0; i < n; i++)
{
scanf("%lld", &tree[i]);
if (tree[i] > max)
max = tree[i];
}
mid = max/2;
min = 0;
while (1)
{
get_total(mid, tree);
if (total == m)
break ;
if (total > m)
{
get_total(mid + 1, tree);
if (total < m)
break ;
min = mid + 1;
mid = (min + max)/2;
}
else
{
max = mid - 1;
mid = (min + max)/2;
}
}
printf("%d", mid);
return 0;
}
C++
복사
문제 풀이
이진탐색으로 m과 total이 동일할때 까지 범위를 max ~ min 으로 줄여가며 값을 구하였다.
또한 m과 딱 떨어지는 값이 없을 경우도 예외처리 해주었다.
min 을 찾아서 하는 것보다 0 부터 나눠가는게 더 빠름
따로 result 를 저장할 필요없이 left - right 값 중 최소 값을 출력할 수 있다.
