3813. [Professional] 그래도 수명이 절반이 되어서는...

 

 

Solution : 이진 탐색 + 파라메트릭스 서치

 

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
using namespace std;

int main() {
	
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	int tc = 0;
	cin >> tc;
	for (int p = 1; p <= tc; p++){
		int n = 0;
		int k = 0;
		cin >> n >> k;
		vector<int> list;
		int a;
		for (int i = 0; i < n; i++) {
			cin >> a;
			list.push_back(a);
		}

		vector<int> problem;
		for (int i = 0; i < k; i++) {
			cin >> a;
			problem.push_back(a);
		}

		int answer = 100000;
		int l = 0;
		int r = 200000;
		while (1) {
			int count = 0;
			int problem_point = 0;
			for(int i=0;i<list.size();i++){
				if (answer >= list[i]) {
					count++;
					if (count == problem[problem_point]) {
						count = 0;
						problem_point++;
					}
				}
				else {
					count = 0;
				}
				if (problem_point >= problem.size())
					break;
			}

			if (problem_point >= problem.size()) {//okey
				r = answer - 1;
			}
			else {
				l = answer + 1;
			}
			if (r < l) {
				answer = l;
				break;
			}
			answer = (r + l) / 2;
		}

		cout << "#" << p << " " << answer << endl;
	}
	
	return 0;
}

 

 

 

swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy