Difference between r1.1 and the current
@@ -1,3 +1,6 @@
아무래도 세 문제 전부 parametric search를 이용한 문제라서 한 페이지에 넣어야 될 듯 싶네여. 페이지 낭비 같음.
* subsequence
{{{#include<iostream>
#include<vector>
@@ -37,3 +40,93 @@
}
}}}
}}}
* 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;
}
}}}
아무래도 세 문제 전부 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;
}
