[Codeforces Round 973(Div. 2)] D. Minimize the Difference

https://codeforces.com/contest/2013/problem/D

Codeforces Round 973(Div. 2) - D. Minimize the Difference

문제 유형 : 스택, 부분합, 그리디

제한 시간: 2초

제한 메모리: 256MB

 

문제

Zhan, tired after the contest, gave the only task that he did not solve during the contest to his friend, Sungat. However, he could not solve it either, so we ask you to try to solve this problem.

You are given an array 𝑎1,𝑎2,…,𝑎𝑛of length 𝑛. We can perform any number (possibly, zero) of operations on the array.

In one operation, we choose a position 𝑖i (1≤𝑖≤𝑛−1) and perform the following action:

• 𝑎𝑖:=𝑎𝑖−1, and 𝑎𝑖+1:=𝑎𝑖+1+1.

Find the minimum possible value of max(𝑎1,𝑎2,…,𝑎𝑛)−min(𝑎1,𝑎2,…,𝑎𝑛).

 

대회가 끝나고 힘든 Zhan은 그의 친구 Sungat에게 못 풀었던 문제를 떠넘깁니다.

그러나 그도 힘들어해서, 당신이 해결해줘야 합니다.

 

정수 배열 a1, a2, ..., an을 받습니다. 0번 이상의 연산을 적용할 수 있습니다.

1<= i <= n-1에 대해서,

ai -= 1 a{i+1} += 1.

 

가능한 (배열의 최대값 - 배열의 최소값)의 최소값을 찾으시오.

 

풀이

문제의 결론은, 배열을 최대한 고른 형태의 비내림차순 형태로 만들어야 한다는 것이다.

이를 위해 스택을 구현할 수 있다.

 

스택을 만들어서, {특정 구간의 평균값, count}를 저장할 수 있다.

배열을 순차적으로 순회하면서, 다음을 반복한다:

 처음 sum에 현재 보고있는 배열의 값을 할당하고, cnt에 1을 넣는다.

 스택에 내용이 있고, 현재 구간의 평균이 이전 구간의 평균(스택의 톱의 first)보다 작은 동안, 다음을 반복한다:
  sum에는 이전 구간의 부분합(즉, 스택의 톱의 first * 스택의 톱의 second)를 누적한다.

  cnt에는 이전 구간의 개수(즉, 스택의 톱의 second)를 누적한다.

  이 작업을 통해서 비내림차순으로 고르게 분포시키기 위한 융화작업이라고 보면 된다.

  

 이제, sum에는 이전구간부터 ~ 현재구간까지의 부분합이, cnt에는 이전구간부터 현재까지의 수가 담겨있다.

 스택에 {sum / cnt, cnt - sum % cnt}, 즉, 새로 구한 평균(단, 소수점 내림)과, 새 구간의 전체수 - sum % cnt를 담는다.

 혹시 나머지가 있는경우, 새로운 구간할당을 위해서 새 구간의 전체수 - sum % cnt개만큼 뺀 것이다.

 나머지가 있는 경우, sum/cnt + 1이 새로 구한 평균의 뒷부분 평균(소수점 올림)이 되고, 이 개수는 sum % cnt개가 된다.

 

스택의 톱이 맨 뒤에 있는 인덱스의 값이 되어, 가장 크고,

스택의 맨 아래에는 맨 앞 인덱스의 값이 담겨있다.

둘의 차를 구하면 된다.

 

코드

C++

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n;

ll solution(vector<ll> &nums, int n) {
  stack<pair<ll, int>> s;

  for (int i = 0; i < n; ++i) {
    ll sum = nums[i];
    ll cnt = 1;

    while (s.size() > 0 && s.top().first >= sum / cnt) {
      sum += s.top().first * s.top().second;
      cnt += s.top().second;
      s.pop();
    }

    s.push({sum / cnt, cnt - sum % cnt});
    if (sum % cnt != 0) {
      s.push({sum / cnt + 1, sum % cnt});
    }
  }

  ll maxVal = s.top().first;
  while (s.size() > 1) {
    s.pop();
  }

  return maxVal - s.top().first;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int t;
  cin >> t;

  for (int i = 0; i < t; ++i) {
    cin >> n;
    vector<ll> nums(n);

    for (int j = 0; j < n; ++j) {
      cin >> nums[j];
    }
    cout << solution(nums, n) << "\n";
  }
  return 0;
}