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
#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; }