Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT135G/
1. Đề bài PTIT135G spoj PTIT
Cho một tập N quân bài, mỗi quân chứa một số nguyên dương. Bạn cần phải chọn ra ba quân bài sao cho tổng các số trên 3 quân bài gần với số M nhất và không vượt quá M.
Input
Dòng 1 chứa 2 số N và M. (N <= 100, M <= 500 000)
Dòng 2 chứa N số nguyên dương, mỗi số không quá 100 000.
Output
In ra tổng 3 quân gần M nhất và không vượt quá M.
Input luôn đảm bảo tồn tại đáp số.
Example
Input:
5 21
5 6 7 8 9
Output:
21
2. Code tham khảo PTIT135G spoj PTIT
Bài này khá đơn giản, làm bằng cách bình thường nhất là o(n^3), có thể cải tiến bằng cách dùng chặt nhị phân, độ phức tạp n^2 log2 n
Code tham khảo N^3
const fi='';
nmax=100;
type data=longint;
var
f:text;
i,m,n:data;
A:array[1..nmax] of data;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n,m);
for i:=1 to n do
read(f,a[i]);
close(f);
end;
procedure xuli;
var i,j,k,res:data;
begin
res:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
if (a[i]+a[j]+a[k]<=M) and (a[i]+a[j]+a[k]>res) then
res:=a[i]+a[j]+a[k];
writeln(res);
end;
begin
docfile;
xuli;
end.Nếu bạn cần code cải tiến vui lòng đề nghị, mình sẽ viết.
Bạn có thể cho mình xin code cải tiến bài Blackjack này được không. gửi cho mình theo địa chỉ sau nhé: [email protected]. cảm ơn bạn.
Chào bạn, hiện tại vì lý do mình còn bận nhiều việc nên chưa thể thực hiện yêu cầu của bạn được. Mong bạn thông cảm. Và với bài như trên thì độ phức tạp khá tuy là O(n^3) nhưng N chỉ 100 nên bạn không cần lo lắng mấy. chỉ khi nào N quá lớn cỡ 10^3->10^4 thì bạn mới cải tiến.0 thì
Mình gợi ý bạn cách làm N^2 log2 N như sau:
– Đầu tiên bạn sắp xếp mảng nhập vào
– Viết function chặt nhị phân tìm số <=M và gần M nhất: tknp(l,r,x:longint):longint; với l, r là giới hạn đoạn đầu cuối cần tìm, x là giá trị mốc mà số tìm dc phải <=X và gần X nhất. sau đó trả về số đó - duyệt 2 dòng for for i:=1 to n-2 do for j:=i+1 to n-1 do IF A[i]+a[j]
res:=max(res,a[i]+a[j]+k);
end;
bạn có thể cho mình xin code cải tiến bài Blackjack này được không. gửi theo mail này cho mình nhé [email protected]. cảm ơn bạn
Cho mình xin code cải tiến mail nhé [email protected] cảm ơn nhiều
Thân chào bạn,
Hiện tại mình do còn bận nhiều việc nên chưa thể hỗ trợ bạn viết code cải tiến, tuy nhiên bạn có thể tham khảo phần bình luận mình đã gửi ở trên, hi vọng sẽ giúp ích được cho bạn.
🙂
Bài này áp dụng tìm kiếm nhị phân ngay thì N^2logN. Sử dụng two-pointer giảm được đến N^2. Nếu sinh tổng 2 số áp dụng tknp có thể giảm tối đa NlogN tùy nhiên phải kiểm tra trùng nên phức tạp hơn chút. N^2 đủ AC bài này rồi.