3074. 입국심사

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_XEokaAEcDFAX7

SW Expert Academy

 

순서를 정해주는 것 보다 최소 시간을 어떻게 구할 것인가에 초점.

가장 최대로 걸리는 line에 모든 사람들이 기다려서 해결하는 것이 가장 최악의 시간이고

0~ 최악의 시간 이 사이 어딘가에 최적의 시간이 존재.

 

이중분할 방식으로 mid 값을 기준으로 사람이 몇명 해결할 수 있는지 구하고

그 사람수가 전체 사람수보다 작은 경우 시간이 더필요하므로 최소 시간을 mid + 1로 변경

반대의 경우 시간이 남는 경우이므로 최대 시간을 mid -1 로 변경

이 안에 사람의 수와 전체 사람수가 일치하는 케이스가 존재하는데 그런 케이스가 여러개일 수 있으므로

그안에서 최소 시간을 찾아주면 끝.

 

 

 

 

#include<iostream>
#include<algorithm>
using namespace std;

long long N, M;
long long t[100000];
long long temp[100000];

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> M;
		int maxa = 0;
		for (int i = 0; i < N; i++)
		{
			cin >> t[i];
			if (t[i] > maxa)
			{
				maxa = t[i];
			}

		}

		long long time1 = 0;
		long long time2 = M * maxa;
		long long result = 987654321987654321;
		while (time1 <= time2)
		{

			long long mid = (time1 + time2) / 2;
			long long person = 0;
			for (int i = 0; i < N; i++)
			{
				person += mid / t[i];
			}

			if (person < M)
			{
				time1 = mid + 1;
			}
			else
			{
				time2 = mid - 1;
				if (result > mid)
				{
					result = mid;
				}
			}


		}
		
		cout << "#" << test_case << " " << result << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}