Subsequence/권영기

아무래도 세 문제 전부 parametric search를 이용한 문제라서 한 페이지에 넣어야 될 듯 싶네여. 페이지 낭비 같음.

• subsequence

#include<iostream>
#include<vector>
using namespace std;
vector <int> e, sum;
int main(void)
{
	int n, s;
	int l, h, m, i, ans = 100020;
	bool flag = false;
	cin>>n>>s;
	e.resize(n + 5);
	sum.resize(n + 5);

	for(i = 1; i<=n; i++){
		cin>>e[i];
		sum[i] = sum[i-1] + e[i];
	}

	l = 0, h = n;
	while(l <= h){
		flag = false;
		m = (l + h) / 2;
		for(i = m; i<=n; i++){
			if(sum[i] - sum[i - m] >= s) {
				flag = true;
				if(ans > m)ans = m;
				break;
			}
		}
		if(!flag)l = m + 1;
		else h = m - 1;
	}
	if(ans == 100020)ans = 0;
	cout<<ans;
	return 0;
}

• drying

#include<iostream>
#include<vector>
using namespace std;
vector <int> laundry;
int main(void)
{

	int n, k, i, ans,  temp = 0;
	int low, high = 0, mid;
	low = 0;
	cin>>n;
	laundry.resize(n + 5);
	for(i = 0; i<n; i++){
		cin>>laundry[i];
	}
	cin>>k;

	for(i = 0; i<n; i++)high += (laundry[i] + (k - 1)) / k;
	ans = high + 1;
	while(low <= high)
	{
		temp = 0;
		mid = (low + high) / 2;
		for(i = 0; i<n; i++){
			if(laundry[i] - mid > 0){
				if(k - 1 <= 0)temp += laundry[i] - mid;
				else temp += (laundry[i] - mid + (k - 2)) / (k-1);
			}
		}
		if(temp <= mid){
			if(ans > mid)ans = mid;
			high = mid - 1;
		}
		else low = mid + 1;
	}
	cout<<ans;
	return 0;
}

• aggressive cow

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> barn;
int main(void)
{

	int low, high, mid, ans = 0;
	int n, c, temp, count;
	int i;
	cin>>n>>c;
	barn.resize(n + 5);
	for(i = 0; i<n; i++){
		cin>>barn[i];
	}
	sort(barn.begin(), barn.begin() + n);
	low = 1;
	high = barn[n - 1] - barn[0];
	
	while(low <= high)
	{
		count = 0;
		mid = (low + high) / 2;
		for(i = 1, temp = 0; i<n; i++){
			if(barn[i] - barn[temp] >= mid){
				count++;
				temp = i;
			}
		}
		if(count >= c-1){
			if(ans < mid)ans = mid;
			low = mid + 1;
		}
		else high = mid - 1;
	}

	cout<<ans;
	return 0;
}