\ # 84 (지선 7 역) [이분 답 + 깊이 우선 검색] 최 적 스케줄 링

Description
[문제 설명]         n 개의 임 무 를 k 개의 병행 가능 한 기계 로 완성 한다 고 가정 합 니 다.퀘 스 트 i 완성 에 필요 한 시간 은 ti 입 니 다.하나의 알고리즘 을 시험 적 으로 설계 하여 이 n 개의 임 무 를 완성 하 는 가장 좋 은 스케줄 을 찾 아 모든 임 무 를 완성 하 는 시간 이 가장 빠르다.  [프로 그래 밍 작업]         주어진 정수 n 과 k, 그리고 임 무 를 수행 하 는 데 필요 한 시간 은 ti, i = 1 ~ n 입 니 다.프로 그래 밍 은 이 n 개의 작업 의 최 적 화 된 스케줄 을 완성 합 니 다.
 
Input
파일 machine. in 에서 입력 데 이 터 를 드 립 니 다.첫 줄 에는 두 개의 정수 n 과 k 가 있다.두 번 째 줄 의 n 개의 정 수 는 n 개의 임 무 를 완성 하 는 데 필요 한 시간 이다.
Output
 계 산 된 모든 작업 을 완료 하 는 가장 빠 른 시간 을 파일 machine. out 에 출력 합 니 다. 
Sample Input

7  3
2  14  4  16  6  5  3

Sample Output

17

이것 은 또 매우 고전적 인 깊이 우선 검색 + 2 점 의 문제 입 니 다.

#include 
#include 
#include 

#define SIZE 102

using namespace std;

int a[SIZE], s[SIZE] = {0}, n, k;

bool cmp(int a, int b)
{
	return (a > b);
}

bool dfs(int x, int mid) //     
{
	int i;
	
	if (x > n) //     ,  
	{
		return true;
	}
	
	for (i = 1; i <= k; i++)
	{
		if (a[x] > mid) //       ,  
		{
			return false;
		}
		
		s[i] += a[x];
		
		if (s[i] <= mid)
		{
			if (dfs(x + 1, mid)) //            
			{
				return true; //          
			}
		}
		s[i] -= a[x];
	}
	
	return false;
}

int main(int argc, char** argv)
{
	int i, sum = 0, l, r, res, mid;
	
	cin >> n >> k;
	for (i = 1; i <= n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	
	sort(a + 1, a + n + 1, cmp);
	
	l = sum / k;
	r = sum;
	while (l <= r) //    ,      
	{
		mid = l + (r - l) / 2; //      
		memset(s, 0, sizeof(s));
		if (dfs(1, mid))
		{
			res = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	
	cout << res << endl;
	
	return 0;
}