CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) - C. Make It Permutation (1300)

C. Make It Permutation

$a_i$ 를 정렬하자.

항상 순열 $p$ 는 $a_i$ 로 끝난다는 가정을 했다.

$c, d \ge 1$ 임을 본다.

$a_i, a_{i+1}$ 사이에 빈 수들이 있으면 그 수들로 끝나는 $p$ 를 만드려면 $[a_i+1, a_{i+1}-1]$ 의 수들을 채워야하는데 그럼 $a_{i+1}$ 를 지우는 비용을 굳이 감수할 필요가 없다.

또한 $a_{i+1}-1$ 보다 작은 수로 끝나려면 그냥 $a_{i+1}$ 만 지우면 $a_{i}$ 로 끝나는 순열이 되므로 더 이득이다.

따라서 모든 $a_i$ 에 대해 순회하며 앞에서 지워야할것, 추가해야할것, 뒤에서 지워야할 것을 관리하면서 최소값을 찾으면 된다.

근데 예제가 하나 다르게 나와서 보니 모두 지운다음 $1$ 하나만 추가하는 엣지케이스만 추가해주면 된다.

예제가 아마 $C$ 번이므로 친절하게 이 엣지케이스를 넣어준거같은데 그렇지 않았으면 몇 번 틀렸을 것이므로 엣지케이스를 잘 고려를 해야겠다.

void solve() {
   int n, c, d;
   cin >> n >> c >> d;
   vi a(n);
   fv(a);
   sort(all(a));
   a.insert(a.begin(), 0);
   n++;
 
   int prefix_add = 0, prefix_remove = 0, suffix_remove = (n - 1) * c;
 
   debug(a);
   int ans = 2e15;
   for (int i = 1; i < n; i++) {
      int j = i;
      int cur = a[i];
      prefix_add += max(0ll, a[i] - a[i - 1] - 1) * d;
      while (j < n && a[i] == a[j]) j++;
      int len = j - i;
      prefix_remove += (len - 1) * c;
      suffix_remove -= len * c;
      mina(ans, prefix_add + prefix_remove + suffix_remove);
      i = j - 1;
   }
   mina(ans, (n - 1) * c + d);
   cout << ans << endl;
}