차이를 최소로
시간 제한1초메모리 제한128 MB
배열에서 각 원소를 1 이상으로 유지하며 총 T번 이하로 감소시켜 인접한 두 원소의 차이의 최댓값을 최소화한 배열을 출력하는 문제입니다.
문제
정수 N개로 이루어진 배열 A가 있다. 한 번의 연산으로 배열의 원소 하나를 골라 그 값을 1 줄일 수 있다. 단, 어떤 원소도 1보다 작아질 수 없다.
이 연산을 최대 T번 수행한 뒤, 인접한 두 원소의 차이의 절댓값 중 최댓값이 가능한 한 작아지도록 배열을 바꾸어 출력하라.
입력
첫째 줄에 N과 T가 주어진다. (2 <= N <= 100000, 1 <= T <= 10^9)
둘째 줄에 배열 A의 원소 A1, A2, ..., AN이 공백으로 구분되어 주어진다. (1 <= Ai < 10^9)
출력
첫째 줄에 조건을 만족하도록 바꾼 배열 A의 원소 A1, A2, ..., AN을 공백으로 구분하여 출력한다.
출력한 배열의 각 원소는 원래 값보다 클 수 없고, 전체 감소 횟수의 합은 T를 넘을 수 없다. 연산을 모두 사용할 필요는 없다.