枚举算法的二分法

题目描述：
有 N 条绳子，它们的长度分别为$L_i$。如果从它们中切割出 K 条长度相同的绳子，这 K 条绳子每条最长能有多长？答案保留到小数点后 2 位。

代码：

#include 

#include 

#include 


#include 


using namespace std;


int sort(double ropes[],int rope_num)
{

	for (int i = rope_num-1;i >= 0;i --)
	{
		for (int j = 0;j < i;j ++)
		{
			if (ropes[j+1] < ropes[j])
			{
				double tmp = ropes[j+1];
				ropes[j+1] = ropes[j];
				ropes[j] = tmp;
			}
		}
	}
	return 0;
}



int split(double  ropes[], int rope_num,int len, int cnt) {

	int total = 0;
	for (int i = 0;i < rope_num;i ++)
	{
		total += ropes[i] / len;
	}
	return total;
}

double makeRope(double  ropes[],int rope_num,int cnt) {

	if (rope_num >= cnt)
	{
		return FALSE;
	}

	double min = 0;

	double max = ropes[rope_num - 1];

	double mid = (min + max) / 2;

	while (  max - min > 0.01)
	{
		mid = (min + max) /2;

		int total = split(ropes, rope_num, mid, cnt);
		if (total < cnt)
		{

			max = mid;

		}else if (total > cnt)
		{
			min = mid;
		}
		else {
			//break;
			min = mid;
		}
	}
	return mid;
}


int main(int argc,char ** argv) {


	double ropes1[8] = { 3.2,1.5,10.8,1024,66.66,888.88,9.1,6.2 };

	double ropes2[8] = { 13.2,21.5,102.8,104,666.66,188.88 ,1402.12,10004.6};

	sort(ropes1,sizeof(ropes1) / sizeof(ropes1[0]));

	sort(ropes2, sizeof(ropes2) / sizeof(ropes2[0]));

	double maxlong1 = makeRope(ropes1, sizeof(ropes1)/sizeof(ropes1[0]), 13);

	printf("rope1 max long :%lf\r\n", maxlong1);

	double maxlong2 = makeRope(ropes2, sizeof(ropes2) / sizeof(ropes2[0]), 18);

	printf("rope2 max long :%lf\r\n", maxlong2);
	_getch();

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103