Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/03/24

SRM 456 CutSticks

| 21:43

http://www.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909

System Test: Passed

長さ target_length 以上の棒が K 本以上作ることができるような target_length のうち最大の値を二分探索で求める.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <cmath>

using namespace std;

const double EPS = 1e-10;

class CutSticks
{
public:

int count_sticks(vector<int> &sticks, int n, int C, double target_length)
{
	int num_sticks = 0;
	for(int i=0;i<n;i++)
	{
		int stick_length = sticks[i];
		if(stick_length<target_length) continue;
		int cut_count = int(stick_length/target_length)-1;
		cut_count = min(cut_count,C);
		num_sticks += cut_count + 1;
		C -= cut_count;
	}
	return num_sticks;
}

double maxKth(vector <int> sticks, int C, int K)
{
	double max=1e10,mid=5e9,min=0.0;
	int loop_count = 0, loop_limit = 1000;
	int n = int(sticks.size());
	while(fabs(max-min)>EPS && (loop_count++<loop_limit))
	{
		if(count_sticks(sticks, n, C, mid)>=K)
			min = mid;
		else
			max = mid;
		mid = (max+min)/2;
	}
	//printf("%.10f\n",mid);
	return mid;
}
};

BuffyBuffy2011/07/22 11:35Thought it woduln't to give it a shot. I was right.

sufoemmgzsufoemmgz2011/07/22 17:37b20kOk <a href="http://kdmhvtcxcpku.com/">kdmhvtcxcpku</a>

bijazpbijazp2011/07/23 18:46cMgwD3 , [url=http://lrwovqzkyseo.com/]lrwovqzkyseo[/url], [link=http://ijbjudvcqwwe.com/]ijbjudvcqwwe[/link], http://ynwvekvmadlb.com/

rcrylkwffqrcrylkwffq2011/07/24 22:186PcbZ6 <a href="http://lyqcjkkrvyqu.com/">lyqcjkkrvyqu</a>

tfpszkfbtfpszkfb2011/07/25 02:49CcttKl , [url=http://helqvkusjrrm.com/]helqvkusjrrm[/url], [link=http://chqujgorbeee.com/]chqujgorbeee[/link], http://mgbsjaskvsjg.com/