Thông Báo:

Mọi thắc mắc xin liên hệ facebook: Bá Sơn
fb.com/sonden2000

Bài tập về chặt nhị phân có lời giải.

Posted by : Unknown Wednesday, March 15, 2017

                                                    BÀI TẬP VỀ CHẶT NHỊ PHÂN
1.Có N cây gỗ, có chiều cao lần lượt là A[1],A[2],..,A[n]. Bạn cần lấy một lượng gỗ độ cao tối thiểu là M bằng cách chặt từ N cây theo cách như sau: chặt tất cả những phần thừa của các cây có độ cao lớn hơn H. Hãy tìm giá trị H lớn nhất để bạn có thể lấy được lượng gỗ tối thiểu là M.
Input
-       Dòng 1 chứa 2 số nguyên N (1<=N<=1 000 000) và M (1 <= M <= 2 000 000 000).
-       Dòng 2 chứa N số nguyên A[1],A[2],…,A[n], là chiều cao mỗi cây gỗ tương ứng (A[i] <= 1 000 000 000, i=1->n). Giả sử luôn tồn tại cách chặt.
Output
Số H duy nhất.
Example
Input:
4 7
20 15 10 17
Output:
15
Giải thích:
Cây 1 chặt được (20-15)=5.
Cây 4 chặt được (17-15)=2.
Tổng số gỗ chặt được nếu H=15 là 7.

 Input:
5 20
4 42 40 26 46
Output
36
Hướng dẫn: chặt nhị phân.
Bước 1: Sắp xếp các cây từ thấp đến cao và tính tổng tất cả các chiều cao bằng T
Bước 2: Đặt thêm cây 0 có độ cao A[0]=0; Tổng S=0;
Bước 3: Duyệt lần lượt từ cây 1 đến cây n tại cây thứ i độ cao chênh lệch sẽ là A[i]-A[i-1] có tất cả (n+1-i) cây có độ cao này chúng ta có S+=(A[i]-A[i-1])*(n+1-i). Tới khi T-S>=m thì dừng.
Bước 4: Như vậy lấy H theo A[i] sẽ không đủ gỗ, lấy theo A[i-1] thì thừa để thừa ít nhất thì phải thêm độ cao K tức là H=K+A[i-1] khi đó T – (S+K*(n+1-i))>=m
suy ra (T-S-M)/n+1-i >= K ta chọn luôn K=(T-S-M)/n+1-i và thu được H=K+A[i-1]
2.
2.
P145SUMG - ROUND 5G - Điểm kiểm soát sân bay
Tại sân bay Nội Bài, một hành khách gồm M người chuẩn bị tham gia chuyến bay. Vì số lượng khách quá lớn nên điểm kiểm soát của sân bay đã được tăng lên thành N điểm. Tại điểm kiểm soát thứ i, cần mất T_i (s) để có thể kiểm tra xong một người  (tính cả thời gian đi bộ từ địa điểm xếp hàng tới điểm kiểm tra này).
Các hành khách sắp xếp theo một hàng đợi. Lần lượt từng người vào một. Hành khách ở đầu hàng đợi được phép đi vào một trạm kiểm soát nào đó nếu như trạm kiểm soát đó đang trống. Tuy nhiên, người đó cũng có quyền đứng chờ để đợi một trạm kiểm soát khác trống để đi tới trạm đó, vì có thể giảm thiểu chi phí thời gian cho cả đoàn (xem ví dụ 1).
Các bạn hãy tính toán xem thời gian nhỏ nhất có thể để đoàn hành khách kiểm tra xong hành lý là bao nhiêu?

Input

Dòng đầu tiên gồm 2 số nguyên N và M, lần lượt là số quầy gửi đồ và số vị khách (N <= 10^5, M <= 10^9). N dòng tiếp theo, mỗi dòng là số nguyên T_i (1 <= T_i <= 10^9).

Output

In ra đáp số của bài toán.

Example

Test 1:
Input:
2 6 
7 
10
Output:
28
Giải thích test 1: Có 2 trạm kiểm soát và 6 hành khách.
Tại t = 0, hành khách 1 và 2 bước vào trạm kiểm tra I và II. Tại t = 7, trạm I trống, và người thứ 3 được phép đi. Tại t = 10, trạm II trống, người thứ 4 bước vào kiểm tra. Tại t = 14, trạm I trống, người thứ 5 tới kiểm tra. Tại t = 20, trạm II trống, nhưng hành khách thứ 6 sẽ đợi thêm một chút, tới t = 21, trạm I trống và hành khách này sẽ tới kiểm tra, tổng chi phí thời gian bằng 28(s).

Test 2:
Input:
7 10
3 
8 
3 
6 
9 
2 
4
Output:
8
HƯỚNG DẪN: Sort tăng dần chiều cao, rồi chặt nhị phân kết quả, với mỗi độ cao đang xét xác định xem có thể chặt đủ m khúc gỗ hay không.
ĐPT O(Nlogn).
3. Bài 1: Chia đồ chơi (6 điểm)
Nhà trẻ vừa nhận được một số lượng lớn các đồ chơi với M màu khác nhau. Các cô trông trẻ sẽ chia các đồ chơi này cho N em bé. Có các nguyên tắc khi chia đồ chơi như sau:
·        Mỗi em bé sẽ chỉ nhận những đồ chơi giống màu nhau.
·        Tất cả các đồ chơi đều phải được sử dụng.
·        Lượng đồ chơi của em bé có nhiều đồ chơi nhất phải nhỏ nhất có thể.
Ví dụ trong trường hợp có 5 em bé, 4 đồ chơi màu đỏ và 7 đồ chơi màu xanh, một cách chia hợp lý sẽ như sau: 2 đỏ, 2 đỏ, 2 xanh, 2 xanh, 3 xanh.
Yêu cầu: Bạn không cần đưa ra cách chia cụ thể mà chỉ cần đưa ra số đồ chơi của em bé có nhiều đồ chơi nhất.
Dữ liệu vào: File văn bản TOY.INP gồm:
- Dòng 1: Gồm hai số nguyên dương N, M (1<= N<= 109, 1<=M <= 3.105) lần lượt là số em bé và số màu đồ chơi.
- M dòng tiếp theo: Dòng i ghi một số nguyên dương ai (1<= ai<= 109) là số đồ chơi có màu i.
Dữ liệu ra: Ghi ra file TOY.OUT là số đồ chơi của em bé có nhiều đồ chơi nhất trong cách chia tối ưu. Chú ý: dữ liệu của bài toán luôn có đáp án.
TOY.INP
TOY.OUT
5  2
4
7
3

4.

CRUELL2 - Cô giáo dạy toán, phần II
Tính lũy thừa là chưa đủ, cô giáo còn có bài tập "khủng" nữa, đó là tìm nghiệm của phương trình có dạng đa thức. Biết rằng các đa thức này có bậc cao nhất là D (1 <= D <= 11) , D là số lẻ và đa thức chỉ có duy nhất 1 nghiệm X trong khoảng -1,000,000 <= X <= 1,000,000; X là nghiệm nếu nó làm cho giá trị của đa thức xấp xỉ 0 hoặc đúng bằng 0.
Cho đa thức cùng với các hệ số thực (-500 <= hệ số bậc i <= 500), hãy tìm giá trị X với độ chính xác đến 0.0005. Khi tìm được X rồi thì ghi ra phần nguyên của X*1,000 (chú ý không làm tròn X).
Ví dụ, đa thức bậc 3: 1.5*x^3 - 10 = 0 có 1 nghiệm X = 1.88207. Như vậy phải ghi ra 1882.
Các bậc của đa thức là tính từ 0..D. 
Không có đáp án nào có nhiều hơn 6 chữ số có nghĩa và mỗi đáp án đều đủ nhỏ để tăng 0.0001 (với kiểu dữ liệu double) thì cũng không làm mất đi tính chính xác.
GỢI Ý: Tìm 1 chiến lược để thu hẹp khoảng của nghiệm cần tìm kiếm mỗi lần "thử" 1 giá trị X nào đó.

Dữ liệu

* Dòng 1: Một số nguyên: D
* Dòng 2..D+2: Dòng i+2 chứa 1 số thực: hệ số của bậc i

Kết quả

* Dòng 1: Một số nguyên là phần nguyên của 1,000 nhân với nghiệm X tìm được.

Ví dụ

Dữ liệu:

3
-10.0
0.0
0.0
1.50

Kết quả:
1882
Hướng dẫn thuật toán: Chặt nhị phân nghiệm của bài toán. Trong quá trình đó ta tính giá trị của hàm số tại left,

right và mid. So sánh nếu F(right)*F(mid) &lt; 0 thì left = mid, nếu F(left)*F(mid) &lt; 0 thì

right = mid. Chặt nhị phân kết thúc khi (left=mid) và (right=mid). Vấn đề này khi học chặt

nhị phân trên số thực các bạn đã được biết.
///code tham khảo:
  1.     Program CRUELL2;
  2. Uses Math;
  3. Const
  4. maxN =500;
  5. Var
  6. n :LongInt;
  7. A :Array[0..maxN] of Real;
  8.  
  9. procedure Enter;
  10. var
  11. i :LongInt;
  12. begin
  13. Read(n);
  14. for i:=0 to n do Read(A[i]);
  15. end;
  16.  
  17. function Cal(x :Real) :Real;
  18. var
  19. i :LongInt;
  20. begin
  21. Cal:=0;
  22. for i:=0 to n do Cal:=Cal+A[i]*Power(x,i);
  23. end;
  24.  
  25. function BS :Real;
  26. var
  27. left,right,mid,cL,cR,cM :Real;
  28. begin
  29. left:=-1000000; right:=1000000; mid:=(left+right)/2;
  30. while (left<>mid) and (right<>mid) do
  31. begin
  32. cM:=Cal(mid); cL:=Cal(left); cR:=Cal(right);
  33. if (cL*cM<0) then right:=mid;
  34. if (cR*cM<0) then left:=mid;
  35. mid:=(left+right)/2;
  36. end;
  37. Exit(mid);
  38. end;
  39.  
  40. Begin
  41. Assign(Input,''); Reset(Input);
  42. Assign(Output,''); Rewrite(Output);
  43. Enter;
  44. Write(Trunc(BS*1000));
  45. Close(Input); Close(Output);
  46. End.




Powered by Blogger.

- Copyright © Luyện thi HSG pascal - blog hướng dẫn tin 11 nâng cao - Powered by Blogger - Designed by Bá Sơn -