[백준 2343] 기타 레슨

https://jaimemin.tistory.com/1130

위 링크를 참조하였다

분류 : 이분탐색

 

요구사항

레코드의 최소길이 구하기

 

풀이

원하는 길이를 찾아야 한다

길이를 정하고 지금 정한 길이가 조건에 부합하는지 확인한다

길이가 오름차순으로 안주어질수도 있어서 정렬하고나서 정답출력하니 틀렸다고 한다

왜그런지 알수가 없당

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
//#include <map>
#include <string>
using namespace std;
int n, m;
int map[100100];
int ssum = 0;
bool check(int now) {
	int sum = 0;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		sum += map[i];
		if (sum > now) {
			sum = map[i];
			cnt++;
		}
	}
	if (now*cnt >= ssum)
		return true;
//	cout << "cnt" << cnt << endl;
	return false;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {  
		scanf("%d", &map[i]); ssum += map[i];
	}
	sort(map, map + n);
	//for (int i = 0; i < n; i++) printf("%d ", map[i]);
	int low = 1;
	int high = 100000;
	int ans = 0;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (check(mid)) {
			low = mid+1;
		}
		else {
			ans = mid;
			high = mid-1;
		}
	//	cout << mid << endl;
	}
	cout <<ans << endl;


}