cf#334-B-More Cowbell-二分
1307 ワード
http://codeforces.com/contest/604/problem/B
タイトル:
n個のものを与え、それぞれの大きさはa[i]であり、 k個の箱ですべてのものを詰めることを要求して、すべての箱はせいぜい2個のものを詰めて、箱は物を詰める前提はです.物の大きさの和は箱の大きさを超えない.
k個の箱の大きさが一致する
最小の箱sizeを求めます.テーマ条件を満たす:k個min-sizeの箱にn個のものを入れる.
二分箱のsize,下界a[n],上界2 e 7.
nlogn
タイトル:
n個のものを与え、それぞれの大きさはa[i]であり、 k個の箱ですべてのものを詰めることを要求して、すべての箱はせいぜい2個のものを詰めて、箱は物を詰める前提はです.物の大きさの和は箱の大きさを超えない.
k個の箱の大きさが一致する
最小の箱sizeを求めます.テーマ条件を満たす:k個min-sizeの箱にn個のものを入れる.
二分箱のsize,下界a[n],上界2 e 7.
nlogn
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
int tm[1000005];
int n,k;
int bin(int x)<span style="white-space:pre"> </span>// x cowball
{
//if (x<n/2) return 0;
if (x<tm[n]) return 0;
int i=1;
int j=n;
int tmp=k;
while (tmp--)
{
int tmpx=x;
tmpx-=tm[j];
j--;
if (tmpx>=tm[i]) i++;
if (i>j) break;
}
if (i>j) return 1;
return 0;
}
int main()
{
int i;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%d",&tm[i]);
}
int l=tm[n];
int r=2e7;
int m;
int ans=-1;
while(l<=r)
{
if (r-l<=1)
{
if (bin(l))
ans=l;
else
ans=r;
break;
}
m=(l+r)>>1;
if (bin(m))
r=m;
else
l=m+1;
}
printf("%d
",ans) ;
return 0;
}