#740 (Div.2) C - Deep Down Below

문제 링크 => https://codeforces.com/contest/1561/problem/C

Problem - C - Codeforces

---

 

Problem tags => binary search, greedy, sortings

 

임의의 동굴에 들어갈 때 맨 앞의 몬스터부터 차례대로 무찔러가면서 1씩 레벨을 업할 수 있다.

 

이때, 몬스터를 무찌르는 과정에서 Hero는 몬스터보다 적어도 레벨이 1 높아야 한다. (이부분이 핵심)

 

즉, 임의의 동굴에 몬스터가 다음과 같이 배치 되었다고 가정하자.

 

Hero (?) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

 

이때 Hero가 해당 동굴에서 최소 어느 레벨이 되어야 모든 몬스터를 무찌를 수 있는지를 차례대로 확인하도록 한다.

 

Hero (6) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

레벨 5 몬스터를 만나면 적어도 (5 + 1) 레벨이 되어야 한다.

 

Hero (10) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

레벨 10 몬스터를 만나면 적어도 (10 + 0) 레벨이 되어야 한다. (5를 무찌르면 11이 되므로)

 

Hero (10) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

레벨 8 몬스터를 만나면 적어도 (8 - 1) 레벨이 되어야 하지만 이전 몬스터를 무찌르지 못하므로 (10 + 0) 레벨이 고정이 되어야 한다.

 

Hero (10) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

레벨 12 몬스터를 만나면 적어도 (12 - 2) 레벨이 되어야 하지만 영웅 레벨이 이전에 최대 레벨이 10이므로 무시한다.

 

Hero (12) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

레벨 15 몬스터를 만나면 적어도 (15 - 3) 레벨이 되어야 한다. (5, 10, 8, 12 차례로 무찌르면 레벨 16이 되므로)

 

Hero (12) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

레벨 11 몬스터를 만나면 적어도 (11 - 4) 레벨이 되어야 하므로 무시한다.

 

Hero (12) ) 5 ,  10  ,  8  ,  12  ,  15  ,  11  ,  16

레벨 16 몬스터를 만나면 적어도 (16 - 5) 레벨이 되어야 하므로 무시한다.

 

즉 i 번째 동굴에 몬스터 k 마리에 대해서 몬스터의 레벨을 ai (1<= i <= k) 라고 할 때, 영웅의 맥시멈 레벨을 구하는 과정은 다음과 같다.

 

HeroLevel(i, k) = max( { a1 + 1, a2 , a3 - 1 , a4 - 2 , ... , ak - (k - 2) } )    <= i 번째 동굴에서 몬스터 k 마리에 대한 영웅의 맥시멈 레벨

 

vector<pair<int, int>> v; 벡터를 선언하여 영웅의 맥시멈 레벨(maxLevel)과 해당 동굴에서의 몬스터 개수(k) 를 동굴마다 push_back 해준다.

 

마지막으로 영웅이 모든 동굴에서 적을 무찌를 수 있는 레벨 중 minimum 이 될 수 있는 레벨을 구하는 방법은 다음과 같다.

 

이 때, 벡터 v에 저장된 n개의 원소들의 쌍을 ( level(i) , k(i) ) (1 <= i <= n) 라고 할 때 다음과 같이 구할 수 있다.

 

minLevel = max( { level(1) , level(2) - k(1), level(3) - (k(1) + k(2)), ... , level(n) - (k(1) + k(2) + ... + k(n-1)) } )   

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

bool compare(pair<int, int> x, pair<int, int> y) {
	return x.first < y.first;
}

void test() {

	vector<pair<int, int>> v;
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		int maxLevel = 0, level, caveCnt, t = 1;
		cin >> caveCnt;
		
		for (int j = 0; j < caveCnt; j++) {
			cin >> level;
			maxLevel = max(maxLevel, level + t);
			t--;
		}
		v.push_back({ maxLevel, caveCnt });
	}

	sort(v.begin(), v.end(), compare);

	int minLevel = v[0].first, sum = v[0].second;
	for (int i = 1; i < v.size(); i++) {
		minLevel = max(minLevel, v[i].first - sum);
		sum += v[i].second;
	}
	cout << minLevel << endl;
}

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

	int t;
	cin >> t;
	while (t--) {
		test();
	}

	return 0;
}