Bài giảng Thuật toán ứng dụng - Bài 1: Pie - Đỗ Tuấn Anh
Phát biểu bài toán
Có N cái bánh và F + 1 người.
Bánh thứ i có bán kính ri và chiều cao là 1.
Mỗi người chỉ được nhận một miếng bánh từ một chiếc
bánh.
Cần chia bánh sao cho mọi người có lượng bánh bằng
nhau (có thể bỏ qua vụn bánh).
Tìm lượng bánh lớn nhất mỗi người nhận được.
Tháng 4, năm 2020
4 / 20
Thuật toán
Gọi p[i] là số người ăn chiếc bánh thứ i. Lượng bánh
mỗi người nhận được là mini{V[i] } với V[i] là thể tích
p[i]
của chiếc bánh thứ i.
Cách 1 - Tìm kiếm theo mảng p : Tìm kiếm vét cạn
mọi giá trị của p.
Cách 2 - Tìm kiếm theo lượng bánh mỗi người
nhận được : Thử từng kết quả, với mỗi kết quả, kiểm
tra xem có thể chia bánh cho tối đa bao nhiêu người.
Tối ưu cách 2 : Sử dụng thuật toán tìm kiếm nhị phân
để tìm kiếm kết quả.
Tháng 4, năm 2020
6 / 20
Code
1
2
sort(r,
r
+
=
N);
3
double lo
0, hi
=
-
4e8 , mi;
4
5
for(int it
=
(lo
0; it
<
/
100; it ++){
2;
6
mi
=
+
=
hi)
0;
N
7
8
int cont
for(int
9
10
11
12
13
14
15
16
17
i
=
1;i >=
0
&& cont <= F; --i)
cont += (int)
floor(PI r[i]
*
*
r[i] / mi);
if(cont
else hi
>
=
F) lo
mi;
= mi;
}
printf("%0.6f", low );
Tháng 4, năm 2020
7 / 20
Code
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
long long count_wood(int height) {
long long sum
for (int
if
=
1;
>
0;
i
i
=
<= n; i++)
(
a[i]
height )
sum += a[i]
return sum;
- height;
}
int main
int
{
l
=
0,
-
r
l
=
>
max(r,a[i]);
while (r
1)
(l
if ( count_wood (mid) >=
else mid;
{
int mid
=
+ r) / 2;
m
) l = mid;
r
=
}
cout << l;
}
Tháng 4, năm 2020
13 / 20
BOOKS1
Có m quyển sách, quyển sách thứ i dày pi trang.
Phải chia số sách trên cho đúng k người, mỗi người sẽ
nhận được một đoạn sách liên tiếp nhau.
In ra cách chia để số trang sách lớn nhất được nhận
bởi một người là nhỏ nhất.
Nếu có nhiều kết quả lớn nhất thì ưu tiên số sách nhận
bởi người 1 là ít nhất, sau đó đến người 2, ...
Tháng 4, năm 2020
14 / 20
Thuật toán 1
Duyệt kết quả của bài toán từ nhỏ đến lớn, cố định số
trang sách lớn nhất được chia cho 1 người.
Với mỗi kết quả ta đi kiểm tra xem có thể chia được cho
đúng k người hay không bằng thuật toán tham lam.
In ra kết quả ngay khi tìm được kết quả thỏa mãn
Độ phức tạp thuật toán O(MAX ∗ n)
Tháng 4, năm 2020
17 / 20
Code 1
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
bool check(long long max_val) {
vector
long long sum
for (int
if (sum
sum += a[i];
else
sum
if (a[i]
<
int
>
pos;
=
0;
i
=
n;
i >= 1; i--) {
+
a[i] <= max_val)
{
}
{
=
a[i];
>
max_val)
{
return false; }
pos. push_back(i); // cac phan tu ngan cach
}
}
if (pos. size () >= k)
** In ket qua **
return true;
{ return false; }
}
Tháng 4, năm 2020
18 / 20
Thuật toán 2
Gọi maxVal là số trang lớn nhất được chia bởi 1 người.
Nhận thấy nếu với giá trị maxVal = x có thể chia dãy
thành ≤ k đoạn thì với maxVal = x + 1 cũng có thể
chia dãy thành ≤ k đoạn với cách chia như cũ.
Ta chặt nhị phân giá trị maxVal.
Độ phức tạp thuật toán O(log MAX ∗ n)
Tháng 4, năm 2020
19 / 20
Code 2
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
bool check(long long max_val) {
// Giong voi ham
o
Code 1
}
int main ()
{
int q; cin >> q;
while (q--)
cin >>
for (int
{
n
>> k;
i
=
1;
0,
i
<= n; i++)
r = MAX;
{ cin >> a[i]; }
long long
while (r
l
=
-
long long mid
l
>
1)
{
=
(l + r) >> 1;
{
if (check(mid ))
r
else
l
=
=
mid;
mid;
}
}
{
}
** In kq tuong ung voi gia tri
r **
}
}
Tháng 4, năm 2020
20 / 20
20 trang
13220
Free
Bạn đang xem tài liệu "Bài giảng Thuật toán ứng dụng - Bài 1: Pie - Đỗ Tuấn Anh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thuat_toan_ung_dung_bai_1_pie_do_tuan_anh.pdf
