BOJ 28359 - 수열의 가치

BOJ 28359 - 수열의 가치

$c_x$ 를 수 $x$가 나오는 횟수라고 하면 정답은 항상 $\text{Max} (c_x \cdot x)+\sum_{i=0}^{n-1}a_i$ 이다.

최대 한 가지의 수만 두 수열에서 모두 포함되게 포함할 수 있기 때문이다.

그냥 $a$를 정렬하기만 해도 답이다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   sort(all(a));
   int ans = acc(a);
   int mx = 0;
   for (int i = 1; i <= n; i++) {
      int c = 0;
      for (int j = 0; j < n; j++) if (a[j] == i)c++;
      maxa(mx, i * c);
   }
   cout << ans + mx << endl;
   for (int i: a) cout << i << ' ';
}