P153PROF PTIT spoj – Quyết chiến
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 ...
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
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 | 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)
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 | 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. |
