Nguồn đề bài: http://www.spoj.com/PTIT/problems/P153PROF/
1. Đề bài P153PROF PTIT spoj
Có một cuộc quyết chiến giữa 2 phe Radiant và Dire. Mỗi phe có N chiến binh, mỗi chiến binh đều biết chỉ số sức mạnh của mình. Cuộc quyết chiến giữa 2 phe phải được tuân thủ luật sau:
Có N vòng đấu, mỗi vòng đấu Radiant và Dire cử ra 1 chiến binh để quyết chiến với bên kia. Chiến binh của bên nào thắng thì bên đó sẽ được 1 điểm, bên thua cuộc được 0 điểm.
Trước khi cuộc quyết chiến diễn ra, thủ lĩnh của cả 2 phe đều biết được thực lực các chiến binh của đối phương. Thủ lĩnh Dire là 1 người tài trí hơn người, ông ta biết cách sắp xếp thứ tự thi đấu sao cho bên mình có thể đạt được nhiều điểm nhất có thể.
Bạn hãy đoán xem với danh sách 2 đội đã cho trước, Dire có thể có tối đa bao nhiêu điểm.
Input
Dòng đầu tiên chứa số N (1 ≤ n ≤ 2*105).
Dòng thứ 2 gồm n số nguyên dương a[1], a[2], …, a[n] là chỉ số sức mạnh của các chiến binh phe Radiant.
Dòng thứ 3 gồm n số nguyên dương b[1], b[2], …, b[n] là chỉ số sức mạnh của các chiến binh phe Dire.
(1 ≤ ai, bi ≤ 2*N).
Giả sử rằng chỉ số sức mạnh của tất cả các chiến binh 2 phe đều khác nhau.
Output
In ra số điểm tối đa Dire có thể đạt được.
Example
Test 1:
Input:
3
3 4 5
1 2 6
Output:
1
Test 2:
Input:
4
4 5 6 2
1 7 3 8
Output:
3
2. Hướng dẫn P153PROF PTIT spoj
-Sắp xếp mảng A, B tăng dần.
– sử dụng 2 biến i (đại diện cho A) và j (đại diện cho B) để duyệt:
– nếu Sức mạnh A[i]<B[j] thì kết quả được thêm 1, ngược lại tức là SM của A[i]>B[j] thì ta cần chọn 1 B[j] khác sao cho lớn hơn A[i], như vậy ta sẽ duyệt chọn j+1 tiếp theo.
– Dừng khi (i=n) hoặc (j=n)
* Dùng Quicksort độ phức tạp N log2 N.
cải tiến dùng đếm phân phối, độ phức tạp O(n).
3. Code tham khảo P153PROF PTIT spoj
Xem code để hiểu rõ hơn (NlogN và O(n)):
a. Code N log2 N
const fi='';
nmax=2*100000;
type data=longint;
mang=array[0..nmax+1] of data;
var
f:text;
A,b:array[0..nmax+1] of data;
n:data;
procedure sort(var A:mang; l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(a,l,j);
if i<r then
sort(a,i,r);
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
for i:=1 to n do
read(f,b[i]);
close(f);
end;
procedure xuli;
var i,j,res:data;
begin
res:=0;
i:=1;
j:=1;
while (i<=n) and (j<=n) do
begin
if b[j]>A[i] then
begin
inc(res);
inc(i);
inc(j);
end
else
inc(j);
end;
writeln(res);
end;
begin
docfile;
sort(a,1,n);
sort(b,1,n);
xuli;
end.
b. Code O(n)
const fi='';
nmax=200000;
type data=longint;
var
f:text;
A,b:array[1..400000] of data;
n:data;
procedure docfile;
var i,j,x,spta,sptb:data;
begin
assign(f,fi); reset(f);
readln(f,n);
fillchar(a,sizeof(a),0);
b:=a;
for i:=1 to n do
begin
read(f,x);
inc(a[x]);
end;
spta:=0;
for i:=1 to 400000 do
for j:=1 to a[i] do
begin
inc(spta);
a[spta]:=i;
end;
for i:=1 to n do
begin
read(f,x);
inc(b[x]);
end;
sptb:=0;
for i:=1 to 400000 do
for j:=1 to b[i] do
begin
inc(sptb);
b[sptb]:=i;
end;
close(f);
end;
procedure xuli;
var i,j,res:data;
begin
res:=0; i:=1; j:=1;
while (j<=n) and (i<=n) do
begin
if b[j]>A[i] then
begin
inc(res);
inc(i);
end;
inc(j);
end;
writeln(res);
end;
begin
docfile;
xuli;
end.
