백준 16401 과자 나눠주기

백준 16401

파라메트릭 서치 문제. 구하고자 하는 것(막자 과자의 최대 길이)을 고정으로 해서 역으로 이분탐색을 응용하면 된다.

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> v;
int solve(int t) {

	int cnt = 0;
	for (auto c : v) {
		cnt += c / t;
	}
	return cnt;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;

	while (m--) {
		int x;
		cin >> x;
		v.push_back(x);
	}

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

	int l = 0;
	int r = v[v.size() - 1];

	while (l < r) {
		int m = (l + r+1) / 2;

		if (solve(m) >= n) {
			l = m ;
		}else if(solve(m)<n){
			r = m - 1;
		}
	}
	cout << l << '\n';

}