[Codeforces Round 973(Div. 2)] B. Battle for Survive

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

Codeforces Round 973(Div. 2) - B. Battle for Survive

문제 유형 : 그리디

제한 시간: 1초

제한 메모리: 256MB

 

문제

Eralim, being the mafia boss, manages a group of 𝑛n fighters. Fighter 𝑖i has a rating of 𝑎𝑖ai.

Eralim arranges a tournament of 𝑛−1n−1 battles, in each of which two not yet eliminated fighters 𝑖i and 𝑗j (1≤𝑖<𝑗≤𝑛1≤i<j≤n) are chosen, and as a result of the battle, fighter 𝑖i is eliminated from the tournament, and the rating of fighter 𝑗j is reduced by the rating of fighter 𝑖i. That is, 𝑎𝑗aj is decreased by 𝑎𝑖ai. Note that fighter 𝑗j's rating can become negative. The fighters indexes do not change.

Eralim wants to know what maximum rating the last remaining fighter can preserve if he chooses the battles optimally.

마피아 보스인 Eralim은 n명의 파이터들을 관리한다.

파이터 i는 a_i만큼의 레이팅을 가진다. Eralim은 n-1개의 경기의 토너먼트를 구성하려고 한다.

아직 탈락하지 않은파이터 i와 j를 골라(1 <= i < j <= n)배틀을 시킨다.

항상 결과로 i는 탈락하고, j가 살아남는다. 그리고 j의 레이팅이 a_i만큼 감소한다.

음수가 될 수 있다.

파이터들의 번호는 변하지 않는다.

Eralim은 최종 우승자가 최대 레이팅을 가지게 하고 싶어한다.

 

입력

테스트 케이스 t(1 <= t <= 10^4)가 주어지고, 

각 테스트 케이스의 첫 줄에는 띄어쓰기로 구분되어 n개의 레이팅이 주어진다.

n의 합은 2 * 10^5를 넘지 않도록 보장된다.

 

출력

각 테스트 케이스별로, 한 줄에 하나의 정수(최종우승자의 대회 후 레이팅)을 반환한다.

 

풀이

결승은 n-1 대 n이 확정이다.
즉, n-1의 레이팅을 최소화 하기 위해, n-1번째 파이터가 n을 제외한 다른 모든 파이터와 싸워 이기고 레이팅을 최소화시킨다.
n-1번째 선수의 레이팅은 a{n-1} - (a1 + a2 + ... + a{n-2})이 되는데, n에게 헌납하므로,
최종 n번째 선수의 결과는 a1 + a2 + ... + a{n-2} - a{n-1} + an이 된다.

 

코드

C++

#include <iostream>
#include <vector>
#define ll long long

using namespace std;


ll solution(vector<int> &ratings, int n) {
  ll res = -1 * ratings[n-2];
  for(int i = 0; i < n-2; ++i) {
    res += ratings[i];
  }
  res += ratings[n-1];
  return res;
}

int main() {
    int t;
    cin >> t;

    int n;
    int r;
    for (int i = 0; i < t; ++i)
    {
        cin >> n;
        vector<int> ratings;
        for (int j = 0; j < n; ++j)
        {
            cin >> r;
            ratings.push_back(r);
        }
        cout << solution(ratings, n) << "\n";
    }

    return 0;
}