CẤU TRÚC dữ LIỆU đặc BIỆT KHI KHAI THÁC STL TRONG c++
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (285.31 KB, 31 trang )
CẤU TRÚC DỮ LIỆU ĐẶC BIỆT KHI KHAI THÁC STL TRONG C++
A. MỞ ĐẦU
I. Lý do chọn đề tài
Trong chuyên đề hội thảo năm 2014 ở Vĩnh Phúc các thầy cơ đã phân tích và trình bày rất
đầy đủ ngun lí hoạt động, cách cài đặt và ứng dụng của một số cấu trúc dữ liệu trừu tượng
như Hàng đợi, Ngăn xếp, Heap-max… và ứng dụng của nó. Tuy nhiên khi cài đặt bằng một
ngơn ngữ lập trình cụ thể người viết phải xây dựng một số hàm và thủ tục để từ đó khai thác
thuận lợi. Ở ngơn ngữ lập trình C++ thì có sẵn các thư viện lưu trữ cấu trúc dữ liệu nâng cao
thường gặp khi xử lí thuật tốn. Có rất nhiều loại cấu trúc dữ liệu đặc biệt, ta quan tâm đến 6
lại cấu trúc:
Hàng đợi hai đầu : dequeue.
Ngăn xếp: stack.
Hàng đợi ưu tiên(đống) : priority-queue.
Tập hợp ánh xạ (set/map)
Vector
Danh sách liên kết (list)
Các thư viện có sẵn giúp chúng ta giảm chi phí về thời gian khi phải xây dựng các
hàm. Đơn giản như trong Pascal các bạn phải viết thủ tục Quicksort (1,n) để sắp xếp mảng
gồm n phần tử thì trong C++ chúng ta chỉ cần gõ dòng lệnh sort(a+1, a+n+1) là được ngay
mảng a sắp xếp không giảm.
Tuy nhiên trong chuyên đề này tôi xin trình bày hai cấu trúc dữ liệu:
Hàng đợi hai đầu : dequeue.
Hàng đợi ưu tiên (đống): priority_queue .
II.Mục đích của đề tài
Hàng đợi ưu tiên và Hàng đợi hai đầu là hai cấu trúc dữ liệu trừu tượng rất hữu ích
trong q trình giải các bài tốn trong các kì thi học sinh giỏi. Về nội dung kiến thức của
hàng đợi hai đầu và hàng đợi ưu tiên đã có rất nhiều tài liệu đề cập đến, trong chun đề này
tơi khơng trình bày lại khái niệm, nguyên lí hoạt động mà chỉ nhắc lại các thao tác cơ bản trên
hàng đợi để đưa vào áp dụng để giải một số bài toán cụ thế, và cũng là tài liệu tham khảo cho
học sinh và giáo viên trong quá trình học tập và giảng dạy các đội tuyển học sinh giỏi.
B. NỘI DUNG:
I HÀNG ĐỢI HAI ĐẦU
1. Khai báo thư viện hàng đợi:
Để sử dụng hàng đợi hai đầu ta phải khai báo thư viện queue: #include <queue>
2. Định nghĩa
Hàng đợi hai đầu là một container cho phép thực hiện các thao tác sau:
+ Thêm một phần tử x vào cuối hàng đợi q: q.push_back(x).
+ Lấy ra một phần tử ở cuối hàng đợi q: q.pop_back().
+ Thêm một phần tử xvào đầu hàng đợi q: q.push_front(x);
+ Lấy ra một phần tử ở đầu hàng đợi q: q.pop_front();
1
Như vậy việc lấy ra và thêm vào diễn ra ở hai đầu hàng đợi
+ q.empty(): cho giá trị true nếu hàng đợi rỗng, giá trị false khi hàng đợi không rỗng.
+ q.front(): cho giá trị của phần tử đứng ở đầu hàng đợi.
+ q.back(): cho giá trị của phần tử đứng ở cuối hàng đơi.
3. Một số ví dụ về khai báo hàng đợi
Ví dụ 1: Khai báo hàng đợi q có các phần tử kiểu int: deque <int> q;
Ví dụ 2: Khai báo hàng đợi q có các phần tử kiểu double: deque <double> q;
Ví dụ 3:Khai báo hàng đợi q có các phần tử kiểu long long:
deque <long long> q;
*Chú ý: Các phần tử trong hàng đợi đều phải cùng kiểu cũng có thể là một kiểu do
người lập trình tự định nghĩa
Ví dụ 1 : Hàng đợi có các phần tử là một cặp:
typedef pair< int, int> II;
deque <II> q;
Ví dụ 2:Hàng đợi có các phần tử là cặp ba số nguyên:
typedef pair
4. Bài tập
Bài tập 1 (dqueue.cpp)
Cho dãy số nguyên a1, a2, …,an và m truy vấn. Truy vấn trên dãy con này là một lệnh
có dạng q(i,j) với ý nghĩa tìm phần tử nhỏ nhất trong dãy con ai, ai+1, …,aj (i≤j).
Cho m truy vấn Q(i1,j1), Q(i2, j2), …, Q(im,jm) thỏa mãn
1.i1≤i2≤….≤im
2. j1≤j2≤….≤jm
Hãy in ra các giá trị là câu trả lời cho các truy vấn tương ứng.
Input: file dqueue.inp gồm có:
Dịng đầu tiên ghi hai số ngun dương n, m (1≤n,m≤105)
Dòng thứ hai ghi n số nguyên a1, a2, …,an.
m dòng tiếp theo, dòng thứ k ghi hai số ik,jk thể hiện cho truy vấn thứ k (dữ liệu đảm
bảo thỏa mãn điều kiện 1 và 2 ở trên)
Output : file dqueue.out gồm m dòng, dòng thứ k ghi kết quả của truy vấn thứ k.
Example :
Dqueue.inp
Dqueue.out
55
1
23145
1
13
1
23
1
34
4
35
45
Thuật tốn: Dễ dàng ta có thể tìm được kết quả của m truy vấn bằng cách sử dụng 2
vòng lặp for như sau:
for (int k=1; k<=m; k++)
2
{
res=oo;
for (int u=i[k]; u<=j[k]; u++) res=min(res, a[u]);
printf(“%d\n”,res);
}
Với tiếp cận cách trên thì độ phức tạp O (m2).
Cải tiến: Ta nhận thấy sau khi tìm được đoạn L=[i1,j1] ta xây dựng một danh sách các
ứng cử viên cho chức “bé nhất” ql≤ql+1≤…..≤qr.
+ Nếu lấy ra một phần tử có giá trị =ql khi đó giá trị bé nhất sẽ là ql+1.
+ Khi thêm vào một phần tử x nếu x
Làm tương tự với qr-1, qr-1… và ta thấy khi đó trong danh sách chỉ cịn phần tử
+ Truy vấn 1 trên đoạn [1,3]: Đầu tiên đưa 2, 3 vào q. Khi đưa 1 vào thì thấy do 1<3
nên đẩy 3 ra, 1<2 nên đẩy 2 ra khi đó đẩy 1 vào và bé nhất là 1in ra 1.
+ Truy vấn 2 trên đoạn [2,3] : đẩy 3 vào và bé nhất là 1 in ra 1.
+ Truy vấn 3 trên đoạn 3-4 đây 4 vào bé nhất là 1 in ra 1.
+ Truy vấn 4 trên đoạn 3-5: đẩy 5 vào bé nhất là 1 in ra 1.
+ Truy vấn 5: trên đoạn 4-5: đẩy 5 vào bé nhất là 4 in ra 4.
Như vậy q hoạt động như hàng đợi 2 đầu do đó ta khai thác queue. Ta sử dụng hàng đợi
q
Chương trình
#include <bits/stdc++.h>
usingname space std;
deque <int> q;
int m,n,a[100001],i[100001],j[100001]
int main() {
scanf(“%d%d\n”,&n,&m);
for (int u=1; u<=n; u++) scanf(“%d”,&a[u]);
for (int k=1; k<=m; k++) scanf(“%d%d\n”,&i[k],&j[k]);
for (int k=1; k<=m; k++) {
for (int u=j[k-1]; u<=j[k]; j++)
{
while (!q.empty() && q.back()>a[u]) q.pop_back();
q.push_back(a[u]);
}
for (int u=i[k-1]; u
printf(“%d\n”,q.front());
}
}
* Nhận xét: Mỗi phần tử vào hàng đợi một lần và ra khỏi hàng đợi khơng q 1 lần. Do
đó độ phức tạp của thuật tốn khơng q n.
3
Bài tập 2: Đủ chất
Cũng như mọi sinh viên, Steve cố gắng đảm bảo ăn uống điều độ, đủ chất và tiết kiệm.
Đã mấy năm rồi, sáng nào Steve cũng ăn hai cái bánh mỳ tròn và uống một cốc sữa đậu nành.
Sữa đậu nành đóng hộp có thể giữ khá lâu, nhưng bánh mỳ thì khơng để dành được quá k
ngày. Giá bánh mỳ thường xuyên biến động. Nhờ tính tình vui vẻ cởi mở, Steve có quan hệ
rất tốt với người bán hàng và biết được giá bánh trong m ngày tính từ hơm nay. Từ đó Steve
có thể lên kế hoạch để tiết kiệm nhất trong việc mua bánh mỳ.
Ví dụ, bánh có thể giữ được trong hai ngày. Giá bánh hôm này là 3 đồng/chiếc, giá
ngày mai là 1 đồng/chiếc và giá ngày kia sẽ là 2 đồng/ chiếc. Kế hoạch chi tiết kiệm của
Steve se là: Hơm nay mua hai chiếc bánh mỳ trịn, ngày mai – sẽ mua 4 chiếc vừa ăn vừa để
dành cho ngày kia. Như vậy Steve phải chi tất cả là 3×2+2×4 = 10.
Yêu cầu: Cho m, k và ci, i =1 ÷ m, trong đó ci – giá một chiếc bánh mỳ tròn bán
ngày thứ i (1 ≤ m, k, ci ≤ 105). Hãy xác định số tiền tối thiểu cần có và số lượng bánh phải
mua ở mỗi ngày.
Input: Vào từ file văn bản foot.inp:
Dòng thứ nhất chứa 2 số nguyên m và k,
Dòng thứ 2 chứa m số nguyên c1, c2, . . ., cn.
Output: Đưa ra file văn bản foot.out: một số nguyên duy nhất là chi phí tối thiểu.
Example:
foot.inp
foot.out
3 2
10
3 1 2
Phân tích bài tốn: Vì bánh mì có thể để được khơng quá k ngày, do vậy ta sẽ duyệt
trong k ngày liên tiếp chọn ngày có giá thấp nhất để mua. Chiến lược để ở ngày i có 2 bánh
mì ăn ta sẽ mua ở ngày có giá bánh mì nhỏ nhất trong đoạn từ :a[i-k+1] ,a[i-k+2], ….,a[i].
Đáp số
Để không phải duyệt nhiều lần để tìm giá trị nhỏ nhất trong mảng a trên đoạn từ [ik+1,i] ta sử dụng hàng đợi hai đầu và xây dựng những ứng cử bé nhất cho vào hàng đợi. Bài
toán trở về giống bài tập 1 ở trên.
Chương trình
#include <bits/stdc++.h>
#include <queue>
#define maxn 100001
using namespace std;
deque <int> q;
int c[maxn],m,k,i[maxn],j[maxn];
long long f[maxn];
void doc()
{
4
scanf("%d%d\n",&m,&k);
for (int u=1; u<=m; u++) scanf("%d",&c[u]);
}
void xuli()
{
memset(f,sizeof(f),0); // để lưu số tiền nhỏ nhất cần phải trả 2 chiếc bánh mì trong mỗi ngày
for (int u=1; u<=m; u++)
{
i[u]=max(1,u-k+1);
j[u]=u;
}
for (int u=1; u<=m; u++)
{
for (int t=j[u-1]+1; t<=j[u]; t++)
{
while (!q.empty() && q.back()>c[t]) q.pop_back();
q.push_back(c[t]);
}
for (int t=i[u-1]; t
f[u]=2*q.front();
}
long long s=0;
for (int u=1; u<=m; u++) s+=f[u];
printf("%I64d",s);
}
int main()
{
freopen(“foot.inp”, “r”,stdin);
freopen(“foot.out”, “w”,stdout);
doc();
xuli();
return 0;
}
Bài 3 Sơn hàng rào
Tuấn Anh muốn sơn lại rào nhà mình. Hàng rào của anh được ghép bởi N tấm ván liên
tiếp, mỗi tấm rộng 1 cm và có chiều cao khác nhau. Để sơn nhanh chóng và dễ dáng hơn,
Tuấn Anh đã mua “Supper Pain Roller Deluxe” (một cây lăn xịn). Cây lăn có chiều rộng x
cm. Mỗi lần dùng Tuấn Anh phải để cây lăn chạm vào bức tường hoàn toàn, nếu khơng sẽ
khơng sơn được gì cả. Mặt khác, lúc nào cũng phải để cho cây lăn song song với mặt đất. Nói
cách khác, Tuấn Anh sẽ chọn ra x tấm ván liên tiếp và sơn từ dưới lên đến độ cao của tấm ván
thấp nhất trong x tấm ván đó.
5
Tuy nhiên, cây lăn không thể giúp Tuấn Anh sơn hết được hàng rào. Phần diện tích cịn
lại khơng thể sơn bằng cây lăn, anh ta sẽ sơn bằng cọ nhỏ. Hãy giúp Tuấn Anh tính xem phần
diện tích phải sơn bằng cọ nhỏ nhất có thể là bao nhiêu?
Input : paint.inp gồm có:
Dịng đầu tiên ghi số ngun N (1≤N≤10 6) là số tấm ván cần phải sơn và số
nguyên X (1≤X≤105).
Dòng tiếp theo ghi N số nguyên dương mô tả chiều cao của từng tấm ván, mỗi số
cách nhau một dấu cách và không quá 106.
Output: paint.out một số nguyên là diện tích nhỏ nhất phải son bằng cọ.
Example
paint.inp
paint.ou
t
5 3
3
5 3 4 4 5
Phân tích bài tốn: Vì cây lăn ln phải đặt chạm hồn tồn vảo bức tường và song
song với mặt đất. Do vậy khi sơn x tấm ván liên tiếp nhau ta chỉ sơn được đến chiều cao của
tấm ván thấp nhất trong x tấm ván ghép với nhau. Như vậy ta sử dụng mảng b để chứa các
giá trị bé nhất trong các đoạn liên tiếp có x giá trị liền nhau :
b1=min(a1,a2,…,ax)
b2=min(a2,a3,…,ax+1)
b3=min(a3,a4,…,ax+2);
……
bn-x+2=0.
….
bn=0.
Để diện tích cịn lại cần phải sơn bằng cọ là nhỏ nhất thì diện tích sơn được bằng lăn là
lớn nhất do đó ta sẽ tìm những giá trị lớn nhất trong mảng b trong các đoạn liên tiếp. Ta sử
dụng mảng c để lưu trữ
C1=max(b1)
C2=max(b1,b2)
C3=max(b1,b2,b3)
C4=max(b2,b3,b4)
…..
Ci=max(bi-x+1,bi-x+2,…bi)
Với mỗi tấm ván k ta sẽ biết được diện tích chưa được sơn là d[k]=a[k]-c[k]. Như vậy
diện tích cần sơn bằng cọ sẽ là s=.
Để có được mảng b và c ta sử dụng hàng đợi hai đầu sẽ giảm được chi phí về thời gian.
Chương trình:
#include <bits/stdc++.h>
#define maxn 1000001
6
using namespace std;
deque <int> q;
int n,a[maxn],x,b[maxn],c[maxn],u[maxn],i[maxn],j[maxn],v[maxn];
void doc()
{
scanf("%d%d",&n,&x);
for (int k=1; k<=n; k++) scanf("%d",&a[k]);
}
void xuli()
{
for (int k=1; k<=n; k++)
{
i[k]=k;
j[k]=k+x-1;
}
for (int k=1; k<=n-x+1; k++)
{
for (int u=j[k-1]+1; u<=j[k]; u++)
{
while (!q.empty() && q.back()>a[u]) q.pop_back();
q.push_back(a[u]);
}
for (int u=i[k-1]; u
if (a[u]==q.front()) q.pop_front();
b[k]=q.front();
}
for (int k=n-x+2; k<=n; k++) b[k]=0;
while (!q.empty()) q.pop_back();// lam rong q
for (int k=1; k<=n; k++)
{
u[k]=max(1,k-x+1);
v[k]=k;
}
for (int k=1; k<=n; k++)
{
for (int t=v[k-1]+1; t<=v[k]; t++)
{
while (!q.empty() && q.back()
}
for (int t=u[k-1]; t
7
c[k]=q.front();
}
long long s=0;
for (int k=1; k<=n; k++) s+=a[k]-c[k];
printf("%I64d",s);
}
int main(){
freopen("paint.inp","r",stdin);
freopen("paint.out","w",stdout);
doc();
xuli();
return 0;
}
Bài tập 4: KẾ HOẠCH PHÓNG TÀU VŨ TRỤ
Cơ quan hàng không vũ trụ Mĩ NASA vừa thực hiện thành công một dự án lớn. Đó là
xây dựng một trạm vũ trụ trên mặt trăng. Công việc trước mắt là duy trì trạm vũ trụ này trong
N ngày. Để vận hành tốt, lúc nào cũng cần có một phi hành gia ở trên trạm vũ trụ. Tuy nhiên,
mỗi phi hành gia không thể ở trên trạm vũ trụ quá M ngày liên tiếp, vì vậy NASA cần lập một
kế hoạch luân phiên các nhà du hành vũ trụ. Chi phí cho việc luân phiên này cũng khác nhau
đối với mỗi ngày và NASA muốn tối thiểu tổng chi phí này. Nhiệm vụ của bạn là đọc các
thông tin và đưa ra một kế hoạch tối ưu. Chú ý rằng ở ngày thứ 1 ln cần có sự thay đổi.
Input: Vào từ file văn bản nasa.inp:
+Dòng thứ nhất ghi hai số N và M (1 ≤ N ≤ 100000, 1 ≤ M ≤ 10000) .
+Dòng thứ i trong N dòng sau ghi số C i chi phí cho việc thay đổi nhà du hành vũ trụ
trong ngày thứ i (0 ≤ Ci ≤ 105).
Output: Ghi ra file nasa.outGồm một dòng duy nhất ghi S là chi phí tối thiểu cho
việc duy trì trạm vũ trụ.
Example:
NASA.IN NASA.OUT
P
9 3
4
1
(Thay người ở
1
các ngày thứ 1,
1
3, 5, 8)
5
1
5
2
1
1
8
Phân tích bài tốn:Gọi f[i] là tổng chi phí ít nhất cần có để duy trì sự sống trên trạm vũ
trụ đến ngày thứ i. Khi đó kết quả cần tìm là f[n].
Cơng thức quy hoạch động
Để tính được f[i] ta dựa vào mảng g[i].
Ta có f[1]=c[1]; g[1]=f[1]+c[2];
g[i+1]=f[i]+c[i+1];
f[i]=min{g[k-m],g[k-m+1],…,g[k-1]}
Để tính f[n] ta làm như sau:
void xuli()
{
f[0]=0; g[0]=c[1]; f[1]=c[1]; g[1]=f[1]+c[2];
for (int i=2; i<=n; i++)
{
f[i]=oo; // oo=10000000009;
if (i>m) for (int j=i-m; j
f[i]=min(g[j],f[i]);
g[i]=f[i]+c[i+1]
;
}
printf("%I64d",f[n]);
}
** Nhận xét với cách duyệt trên thì độ phức tạp của thuật tốn O (n2). Để cải tiến ta sử dụng
hàng đợi hai đầu.
Chương trình cải tiến:
#include <bits/stdc++.h>
#define maxn 1000001
using namespace std;
deque <int> q;
int n,m,c[maxn];
long long f[maxn],g[maxn];
void doc()
{
scanf("%d%d",&n,&m);
for (int k=1; k<=n; k++) scanf("%d",&c[k]);
}
void xuli()
{
f[0]=0; g[1]=c[1]; f[1]=c[1]; g[2]=f[1]+c[2];
q.push_back(g[1]);
for (int i=2; i<=n; i++)
{
while (!q.empty() && q.back()>g[i]) q.pop_back();
q.push_back(g[i]);
9
if (i>m) if (q.front()==g[i-m]) q.pop_front();
f[i]=q.front();
g[i+1]=f[i]+c[i+1];
}
printf("%I64d",f[n]);
}
int main()
{
freopen("nasa.inp","r",stdin);
freopen("nasa.out","w",stdout);
doc();
xuli();
return 0;
}
Bài 5 Dãy dài bậc k
Cho dãy số nguyên a1, a2, ..,an. Một dãy con của dãy đã cho là dãy các phần tử liên
tiếp nhau. Dãy con ai, ai+1, …,aj được gọi là dãy con đều bậc k nếu như chênh lệch giữa hai số
bất kỳ trong dãy này không vượt quá k. Hãy tìm dãy con đều bậc k có độ dài lớn nhất
Input: sequarek.inp
Dòng đầu tiên ghi hai số nguyên dương n, k (1≤n≤106,1≤k≤109)
Dòng thứ hai ghi n số nguyên a1, a2, …,an (│ai│≤ 109)
Output: một số nguyên duy nhất là độ dài của dãy con tìm được
Example:
Sequarek.inp
Sequarek.out
53
4
21345
Phân tích bài tốn: Để tìm được dãy con đều bậc dài nhất ta tìm đoạn [u,v] mà (v-u+1)
max thỏa mãn amax-amin≤k .
Ta dễ dàng có được kết quả cần tìm thơng qua đoạn chương trình :
res=0;
for( int v=1; v<=n; v++)
{
fmax=-oo; fmin=oo;
for (int u=v; u>=1; u--)
{
fmax=max(fmax,a[u]); fmin=min(fmin,a[u]);
if (fmax-fmin>k ) break;
}
res=max(res,v-u+1);
}
Do 1≤n≤106 nên để cải tiến chương trình ta sử dụng hàng đợi sẽ giúp chương trình
chạy nhanh với n lớn. Để tiết kiếm chi phí thời gian ta dùng hai hàng đợi q và p trong đó hàng
đợi q có đặc điểm phần tử đứng trước có giá trị lớn hơn hoặc bằng giá trị của phần tử đứng
10
sau. Cịn hàng đợi p có đặc điểm phần tử đứng trước có giá trị nhỏ hơn hoặc bằng giá trị của
phần tử đứng sau. Để kiểm tra xem a[v]-a[u]>k ta sử dụng q.front-p.front>k .
Chương trình :
#include <bits/stdc++.h>
#include <queue>
#define maxn 1000001
#define oo 2000000009
using namespace std;
deque <int>q,p;
int a[maxn],n,k,res;
void doc()
{
scanf("%d%d",&n,&k);
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
}
void xuli()
{
int u=1;
for (int v=1; v<=n;v++)
{
while (!q.empty() && q.back()
while (!p.empty() && p.back()>a[v]) p.pop_back();
p.push_back(a[v]);
while (q.front()-p.front()>k)
{
if (q.front()==a[u]) q.pop_front();
if (p.front()==a[u]) p.pop_front();
u++;
}
res=max(res,v-u+1);
}
printf("%d",res);
}
int main()
{
freopen("seqarek.inp","r",stdin);
freopen("seqarek.out","w",stdout);
doc();
xuli();
return 0;
11
}
Bài tập 6. Ếch săn mồi
Có m bậc thang đánh số từ 1 đến m từ trên xuống dưới. Mỗi bậc thang được chia đều
thành n ơ. Ơ thứ j của bậc thang i được gọi là ô (i,j) và trên đó có lượng thức ăn aij.
Một con ếch muốn đi săn mồi trên những bậc thang. Ếch được xuất phát từ một ô tùy ý
trên bậc thang 1 và nhảy dần xuống bậc thang m. Khi nhảy tới ô nào thì ếch sẽ ăn hết thức ăn
trong ơ đó. Tuy nhiên có một hạn chế là từ ơ (x,y) chú ếch chỉ được phép nhảy sang ô (x’,y’)
nếu:
Yêu cầu : Tìm một cách đi kiếm ăn cho chú ếch sao cho tổng lượng thức ăn kiếm được
là lớn nhất.
Input frog.inp gồm có:
- Dịng 1 chứa ba số ngun dương m, n, k ≤1000.
- M dòng tiếp theo, dòng thứ i chứa n số nguyên dương , số thứ j là aij≤109.
Output frog.out gồm có:
- Dịng 1 ghi tổng lượng thức ăn kiếm được.
- M dòng tiếp theo, dòng thứ i ghi một số nguyên là số hiệu ô đi qua trên bậc
thang i.
Example
Frog.inp
Frog.out
352
18
43211
3
43549
5
12375
4
Phân tích bài tốn:Gọi f[i][j] là số lượng thức ăn lớn nhất mà ếch kiếm được khi di
chuyển đến ơ (i,j) ta có cơng thức quy hoạch động f[i][j]= a[i][j]+max{f[i-1][j+t],t=-k..k}
Đáp số cần tìm chính là max{f[m][j], j=1..n}.
Để tính f[i][j] ta phải sử dụng ba vịng lặp for dẫn đến chương trình chạy chậm tức là
khơng hiệu quả. Để giảm chi phí thời gian ta sử dụng một hàng đợi hai đầu để tính f[i][j].
Hoạt động của hàng đợi q luôn đưa vào cuối hàng đợi phần tử có giá trị lớn hơn phần
tử trước đó. Phần tử đầu hàng đợi được lấy để tính mảng f khi thỏa mãn khơng q k.
Chương trình :
#include <bits/stdc++.h>
#define maxn 1001
using namespace std;
deque <int> q;
int n, m,k,a[maxn][maxn],tr[maxn][maxn],x[maxn];
long long f[maxn][maxn],res;
void doc()
{
12
scanf("%d%d%d",&m,&n,&k);
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++) scanf("%d",&a[i][j]);
}
void xuli()
{
for (int i=1; i<=n; i++) {
f[1][i]=a[1][i];
tr[1][i]=0;
}
for (int i=2; i<=m; i++)
{
int u=0;
int v=0;
while (!q.empty()) q.pop_back();
for (int j=1; j<=n; j++)
{
while (v
v++;
while (!q.empty() && f[i-1][q.back()]
}
while (u
if (f[i-1][u]==f[i-1][q.front()]) q.pop_front();
u++;
}
f[i][j]=a[i][j]+f[i-1][q.front()];
tr[i][j]=q.front();
}
}
res=0; int id=1;
for (int i=1; i<=n; i++)
if (res
res=f[m][i];
13
id=i;
}
int slx=0; int u=m;
while (u>0)
{
x[++slx]=id;
id=tr[u][id];
u--;
}
printf("%I64d\n",res);
for (int i=m; i>=1; i--) printf("%d\n",x[i]);
}
int main()
{
freopen("frog.inp","r",stdin);
freopen("frog.out","w",stdout);
doc();
xuli();
}
Bài tập 7: THỜI TRANG CỦA BÒ
Tại hội diễn thời trang mới nhất. Mẫu thời trang đang thịnh hành của các con bị là có
hai vệt trắng trên da của nó. Nơng dân John đã mua một con bị như vậy. Thật khơng may,
thời trang ln thay đổi nhanh chóng và bây giờ mẫu thời trang thịnh hành lại là chỉ có một
vệt trắng trên da(‼!).
Nơng dân John muốn tạo lại mẫu thời trang mới cho con bị của mình bằng cách trộn hai vệt
trắng thành một. Da của con bị có thể mơ tả như là một lưới n hàng, m cột (1≤n,m≤50) gồm
các kí tự dạng:
…………….
..xxxx….xxx…
…xxxx….xx…
.xxxx……xxx..
……..xxxxx…
………xxx….
Ở đây, kí tự ‘X’ xác định một điểm trắng. hai điểm trắng ‘X’ cùng một vệt trắng nếu nó
được nối với nhau bởi một dãy các điểm chung cạnh cùng màu trắng. Có đúng hai vệt trắng
như vậy.
14
Nông dân John dùng một cái bút vẽ nhỏ để thực hiện việc trộn hai vệt trắng thành một.
Cụ thể anh ta sẽ tô một số ô thành màu trắng để sau khi tơ trên tấm da chỉ cịn một vệt. Trong
ví dụ trên anh ta cần tơ 3 ơ thành màu trắng (được đánh dấu bởi ‘*’ trong hình dưới đây):
…………….
..xxxx….xxx…
…xxxx*...xx…
.xxxx..**..xxx..
……..xxxxx…
………xxx….
Hãy giúp nông dân John xác định số lượng ơ ít nhất cần tơ thêm để có được mẫu thời
trang mới.
Input pageant.inp gồm có:
Dịng đầu tiên ghi hai số nguyên dương n, m .
Dòng 2 đến n+1 : Mỗi dịng chứa một xâu kí tự độ dài m chỉ gồm kí tự ‘X’ hoặc
‘.’ Mơ tả hình dạng trên da con bò.
Output : pageant.out: Một số nguyên duy nhất là số lượng ơ ít nhất cần phải tơ thành
màu trắng.
Example
Pageant.inp
Pageant.out
6 16
3
................
..xxxx....xxx...
...xxxx....xx...
.xxxx......xxx..
........xxxxx...
.........xxx....
Hướng dẫn: Để giải Bài tốn trên ta phải tiến hành qua hai bước:
B1 : Tìm số thành phần liên thơng
xp
B2: Tìm đường đi ngắn nhất giữa hai thành phần liên thơng.
kt
Chương trình :
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> II;
int m,n,kq,slt,color[55][55],cl[55][55],kc[55][55];
char a[55][55];
int dh[5]={0,0,-1,0,1};
int dc[5]={0,1,0,-1,0};
deque <II> q;
15
void doc()
{
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) scanf("%c",&a[i][j]);
scanf("\n");
}
}
void bfs(int i, int j)
{
while (!q.empty()) q.pop_front();
q.push_back(II(i,j));
color[i][j]=slt;
while (!q.empty())
{
int u=q.front().first;
int v=q.front().second;
q.pop_front();
for(int k=1;k<=4;k++)
{
int u1=u+dh[k];
int v1=v+dc[k];
if(1<=u1 && u1<=n && 1<=v1 && v1<=m && a[u1][v1]=='x' && color[u1]
[v1]==0)
{
color[u1][v1]=slt;
q.push_back(II(u1,v1));
}
}
}
}
void timtplt()
{
memset(color,0,sizeof(color));
slt=0;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
if (a[i][j]=='x' &&color[i][j]==0)
{
slt++;
bfs(i,j);
}
}
16
void bfs2()
{
while(!q.empty())
{
int u= q.front().first;
int v= q.front().second;
q.pop_front();
for(int k=1;k<=4;k++)
{
int u1=u+dh[k];
int v1=v+dc[k];
if(1<=u1 && u1<=n && 1<=v1 && v1<=m && cl[u1][v1]==0)
{
cl[u1][v1]=1;
kc[u1][v1]=kc[u][v]+1;
q.push_back(II(u1,v1));
if(color[u1][v1]==2) {kq=kc[u1][v1]-1; return;};
}
}
}
}
void timduongdi()
{
timtplt();
while(!q.empty()) q.pop_front();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(color[i][j]==1) {q.push_back(II(i,j)); cl[i][j]=1;kc[i][j]=0;};
bfs2();
cout<
int main()
{
freopen("pageant.inp","r",stdin);
freopen("pageant.out","w",stdout);
doc();
timduongdi();
return 0;
}
17
II. HÀNG ĐỢI ƯU TIÊN (ĐỐNG)
1. Khái niệm
Hàng đợi ưu tiên là một kiểu dữ liệu trừu tượng tập hợp đặc biệt, trong đó mỗi phần tử
có một độ ưu tiên nào đó.Độ ưu tiên của phần tử thường là một số, theo đó, phần tử có độ ưu
tiên nhỏ nhất sẽ được ‘ưu tiên’ nhất. Một cách tổng quát thì độ ưu tiên của một phần tử là một
phần tử thuộc tập hợp được xếp theo thứ tự tuyến tính.
Hàng đợi ưu là một loại container adaptor, được thiết kế đặc biệt để phần tử ở đỉnh
luôn luôn là phần tử có độ ưu tiên lớn nhất so với các phần tử khác.Nó giống như một heap,
mà ở đây là heap max, tức là phần tử có độ ưu tiên lớn nhất có thể được lấy ra và các phần tử
khác được chèn vào bất kì.Lợi ích của cấu trúc hàng đợi ưu tiên luôn cho chúng ta sẵn các
thao tác chỉ việc khai thác mà không mất thời gian xây dựng.
2. Khai báo thư viện:
Để khai thác và sử dụng hàng đợi ưu tiên ta phải khai báo thư viện queue:
#include <queue>
3. Các thao tác
Hàng đợi ưu tiên (đống) là một container cho phép thực hiện các thao tác sau:
+ Thêm một phần tử x vào hàng đợi ưu tiên h: h.push(x).
+ Lấy ra khỏi hàng đợi ưu tiên phần tử có giá trị lớn nhất : h.pop().
** Như vậy việc lấy ra và thêm vào diễn ra một đầu.
+ h.empty(): cho giá trị true nếu hàng đợiưu tiên khơng có phần tử nào, giá trị false khi
hàng đợi ưu tiên không rỗng.
+ h.top(): cho giá trị lớn nhất của đống h.
+ h.size(): cho biết số lượng phần tử trong đống h.
4. Một số ví dụ về khai báo hàng đợi ưu tiên
Ví dụ 1: khai báo hàng đợi ưu tiên q có các phần tử kiểu int.
priority_queue <int> q;
Ví dụ 2: Khai báo hàng đợi ưu tiên q có các phần tử kiểu double;
priority_ queue <double> q;
*Chú ý: Các phần tử trong hàng đợi đều phải cùng kiểu cũng có thể là một kiểu do
người lập trình tự định nghĩa
Ví dụ 1: Khai báo Hàng đợi ưu tiên q có các phần tử mà mỗi phần tử là một cặp dữ liệu
typedef pair< int, int> II;
priority_queue <II> q;
Ví dụ 2: Hàng đợi ưu tiên q có các phần tử mà mỗi phần tử là một cặp ba số nguyên:
typedef pair
5. Bài tập áp dụng
Để hiểu và vận dụng khai thác được hàng đợi ưu tiên vào giải các bài tốn tơi thường
cho học sinh làm một số bài tập từ đơn giản nhất đến khó dần để các em học sinh dễ tiếp thu.
Bài tập 1. Hàng đợi ưu tiên Max
Cho trước một danh sách rỗng. Người ta xét hai thao tác trên danh sách đo:
18
- Thao tác “+V” (ở đây V là một số tự nhiên≤10 9): Nếu danh sách đang có ít hơn 15000
phần tử thì thao tác này bổ sung thêm phần tử V vào danh sách , nếu không thao tác
này khơng có hiệu lực.
- Thao tác “- ”: Nếu danh sách đang khơng rỗng thì thao tác này loại bỏ tất cả các phần
tử lớn nhất của danh sách . Nếu khơng thao tác này khơng có hiệu lực.
Ví du: Với danh sách ban đầu rỗng:
- Nếu ta thực hiện liên tiếp các thao tác : +1, +3, +2, +3 ta sẽ được danh sách (1,3,2,3)
- Thực hiện thao tác -, ta sẽ được danh sách (1,2)
- Thực hiện hai thao tác +4 ta sẽ được danh sách (1,2 ,4, 4)
- Thực hiện thao tác – ta sẽ được danh sách (1,2)
- Tiếp tục với các thao tác +2, +9, +7, +8 ta sẽ được danh sách (1, 2, 2, 9, 7, 8)
- Cuối cùng ta thực hiện thao tác -, ta còn lại danh sách (1, 2, 2, 7, 8).
Vấn đề đặt ra là cho trước một dãy không quá 100000 thao tác.Hãy xác định những giá trị
số nào còn lại trong danh sách , mỗi giá trị chỉ được liệt kê một lần.
Input io.inp gồm nhiều dòng, mỗi dòng ghi một thao tác . Thứ tự các thao tác trên các
dòng liệt kê theo đúng thứ tự sẽ thực hiện.
Output io.out gồm có 2 dịng:
Dịng 1: Ghi số lượng những giá trị còn lại trong danh sách .
Dòng 2: Liệt kê những giá trị đó theo thứ tự giảm dần.
Example
Io.inp
Io.out
+1
4
+3
8721
+2
+3
+4
+4
+2
+9
+7
+8
Hướng dẫn: Ta nhận thấy sau mỗi thao tác thêm vào thì danh sách mới ln được sắp
xếp theo thứ tự giảm dần, còn khi loại bỏ phần tử trong danh sách thì phần tử bị loại bỏ ln
có giá trị lớn nhất. Với bài toán trên theo cách làm thơng thường thì sau khi thêm một phần
tử vào danh sách ta lại phải sắp xếp lại danh sách đó theo thứ tự giảm dần. Việc đó mất nhiều
thời gian vì ta phải duyệt lại cả danh sách. Ta nhận thấy dựa vào tính chất của hàng đợi ưu
tiên việc đưa ra dãy số còn lại sau 100000 thao tác trở lên đơn giản nhiều. Đây chính là lợi
thế của hàng đợi ưu tiên.
Chương trình
19
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int n, x[15001];
priority_queue <int> h;
char loai;
void them()
{
scanf("%d",&n);
if (h.size()<15000) h.push(n);
}
void bot()
{
scanf("\n");
if (!h.empty())
{
int t=h.top();
while (t==h.top() && !h.empty()) h.pop();
}
}
void inkq()
{
int slx=0;
while (!h.empty())
{
x[++slx]=h.top();
while (!h.empty() && h.top()==x[slx]) h.pop();
}
printf("%d\n",slx);
for (int i=1; i<=slx; i++) printf("%d ",x[i]);
}
int main()
{
freopen("io.inp","r",stdin);
freopen("io.out","w",stdout);
while (scanf("%c",&loai)==1)
{
switch(loai){
case '+': them(); break;
case '-':bot(); break;
}
}
20
inkq();
return 0;
}
** Chú ý khi đã khai báo thư viện : #include <bits/stdc++.h> thì khơng cần phải khai báo
#include <queue>
Bài tập 2.BÍ HIỂM
Bà của Ellenora thường ra cho cháu gái mình những bài tốn đố mà Elly coi là bí hiểm.
Buổi tối vừa rồi bà đố Elly bài toán sau:
“Ở cửa hàng cạnh nhà ta có k mặt hàng với giá khác nhau từ 1 đến k . Bà có n đồng
tiền mệnh giá a1, a2, ….an. Bà định sang bên đấy mua một mặt hàng nào đó, trả đúng giá
của nó mà khơng phải nhận lại tiền thừa. Nhưng bà đã già quá rồi. Bà không muốn mang tất
cả tiền của mình đi, có thể lẫn hoặc rơi mất, vì vậy bà chỉ mang theo một số đồng đầu tiên.
Vậy bà phải mang theo bao nhiêu đồng tiền để mau được mặt hàng bất kỳ.
Chỉ mất vài giây Elly đã đưa ra được câu trả lời và nghĩ thầm trong bụng “ Ơi , bà ơi, lại
những bài tốn giải thuật quá chán”.
Bạn có thể đua tài với Elly bằng cách viết chương trình giải bài tốn này được khơng?
Input: riddle.inp gồm có:
- Dịng đầu tiên chứa số ngun T-Số lượng tests trong file.
- Mỗi test cho trên hai dòng:
+ Dòng thứ nhất chứa hai số nguyên n và k (1≤n≤105,1
+ Dòng thứ 2 chứa n số nguyên a1, a2, …,an (0
khơng có cách mang theo thì đưa ra -1.
Example
Riddle.inp
Riddle.out
3
4
7 10
3
1234567
-1
33
241
36
314
Hướng dẫn: Bài tốn có thể phát biểu lại như sau: Có k mặt hàng mệnh giá 1, 2, 3,
..,k. có n số tờ tiền mệnh giá a1, a2, ..,an. Hỏi phải chọn số m bé nhất là bao nhiêu để có các
tờ tiền a1, a2, ..am có thể trả tiền cho bất kỳ mặt hàng nào ở trên.
Như vậy gọi T là số mà từ 0, 1, 2, ..,T đều trả được tiền. Xét tờ thứ i có giá a[i].
Nếu a[i]>T+1 thì số tiền lớn nhất trả được sẽ là T.
Nếu a[i]<=T+1 thì số tiền trả có thể trả được là T+a[i].
Nếu T≥k thì dừng lại khơng xét.
Ví dụ: với n=10, k=20, a={2, 4, 7, 1, 3, 10, 6, 5, 9}
21
Lúc đầu T=0
Xét với a1=2>T+1 giữ lại 2 vào mảng h
Với a2=4>T+1 giữ lại 4 vào mảng h
Với a3=7>T+1 giữa lại 7 vào mảng h
Với a4=1<=T+1 khi đó T=0+1=1. Trong mảng h có 7 4 2
Lấy 2 trong mảng h, xét thấy 2<=T+1 khi đó T=1+2=3
Lấy 4 trong mảng h , xét thấy 4<=T+1 khi đó T=3+4=7
Lấy 7 trong mảng h, xét thấy 7<=T+1 khi đó T=7+7=14
Xét với a5=3<=T+1 khi đó T=3+14=17
Xét với a6=10<=T+1 khi đó T=17+10=27
T=27>k=20 q trình dừng lại vậy m=6 (với 6 số đầu tiên để mua được bất kỳ mặt hàng
nào)
Ta thấy mảng h luôn sắp xếp giảm dần. Như vậy nếu dùng hàng đợi ưu tiên thì ln có
danh sách sắp xếp tăng dần thì ta sẽ lưu trữ thay vì lưu trữ a[i] ta sẽ lưu trữ -a[i].
Chương trình
#include <bits/stdc++.h>
#define maxn 100001
using namespace std;
priority_queue <int> h;
int n,k,t, a[maxn];
void doc()
{
scanf("%d%d",&n,&k);
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
}
void xuli()
{
long long s=0;int id=0;
while (!h.empty()) h.pop();
for (int i=1; i<=n; i++)
{
h.push(-a[i]);
while (!h.empty() && -h.top()<=s+1)
{
s+=-h.top();
h.pop();
}
if (s>=k) {id=i; break;}
}
22
if (id==0) id=-1;
printf("%d\n",id);
}
int main()
{
freopen("riddle.inp","r",stdin);
freopen("riddle.out","w",stdout);
scanf("%d",&t);
for (int u=1; u<=t; u++)
{
doc();
xuli();
}
return 0;
}
Bài tập 3.Lập lịch
Siêu thị máy tính Deep Blue là máy tính mạnh nhất thế giới trong những năm cuối cùng
của thế kỷ XX. Nó đã từng thắng cả vua cờ Kasparop. Vì vậy, có rất nhiều bài tốn được giao
cho nó thực hiện . Tuy nhiên khơng phải lúc nào nó cũng hồn thành cơng việc được giao.
Có n chương trình thực hiện trên Deep Blue. Biết:
Pi là thời gian cần thiết để hồn thành chương trình thứ i.
Di là thời hạn phải giao nộp kết quả của chương trình thứ i cho bên đặt hàng.
Máy tính bắt đầu hoạt động tại thời điểm 0. Mỗi chương trình cần phải thực hiện liên tục
kể từ khi bắt đầu cho đến khi kết thúc, không cho phép ngắt quãng . Giả sử ci là thời điểm
hồn thành chương trình thứ i. khi đó nếu ci≤di thì nói chương trình này hồn thành đúng
hạn, trường hợp ngược lại là hồn.
u cầu: Tìm trình tự thực hiện các chương trình sao cho số chương trình hồn thành
khơng đúng hạn là nhỏ nhất.
Input: tardy.inp gồm có:
- Dịng đầu tiên chứa số ngun dương n (0
- Dịng đầu tiên ghi số lượng chương trình hồn thành khơng đúng hạn
- Dòng tiếp theo ghi n số nguyên dương là chỉ số các chương trình được thực hiện
theo thứ tự tìm được.
Example
Tardy.inp
Tardy.out
6
2
241231
134625
356678
23
Hướng dẫn: quan sát dãy d theo thứ tự tăng dần
P
D
2
4
1
2
3
1
3
5
6
6
7
8
Chọ Loạ Chọ Chọ Loạ Chọ
n
i
n
n
i
n
Xét tại thời điểm 3 chỉ làm được công việc là 2. Xét tại thời điểm 5 chỉ cịn 5-3=2 đơn vị
thời gian khi đó khơng thể hồn thành cơng việc trong thời hạn là 4 (loại) xét tại thời điểm 6
công việc 1, 2 đơn vị thời gian được chọn, tại thời điểm 7 cơng việc 3 khơng thể hồn thành
(loại) thời điểm 8 có 1 đơn vị thời gian hồn thành được. như vậy tổng thời gian hoàn thành
đúng hạn là 2+1+2+1=6 .
Như vậy thuật tốn : săpx sếp các cơng việc sao cho d1≤d2≤…..≤dn.
Giả sử thời điểm sẵn sàng làm việc là T.
Xét công việc i:
+ Nếu làm công việc i sẽ mất thời gian là T+p[i]. Nếu T+p[i]>di thì bỏ cơng việc đã làm
mà có p lớn nhất. những cơng việc nào bỏ đi ta gán cho nó giá trị oo. Khi sắp xếp mảng d kéo
theo mảng p thay đổi ta sử dụng kiểu dữ liệu pair và thêm mảntg id để đánh số hiệu của từng
công việc
Như vậy ta dùng mảng a lưu (d, p, id), đống h lưu ( p,d,id).
Chương trình :
#include <bits/stdc++.h>
#define maxn 100001
#define ft first
#define scf second.first
#define scsc second.second
#define oo 1000000001
using namespace std;
typedef pair<int, int> II;
typedef pair<int,II> III;
III a[maxn];
II kq[maxn];
priority_queue <III> h;
int n, p[maxn],d[maxn];
long long s[maxn],ds,smax,smin;
void doc()
{
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d",&p[i]);
for (int i=1; i<=n; i++) scanf("%d",&d[i]);
}
24
void xuli()
{
for (int i=1; i<=n; i++) {
a[i].ft=d[i]; a[i].scf=p[i]; a[i].scsc=i;
}
sort(a+1, a+n+1);
long long t=0; III x;
for (int i=1; i<=n; i++) {
x.ft=a[i].scf;
x.scf=a[i].ft;
x.scsc=a[i].scsc;
h.push(x);
t+=x.ft;
d[x.scsc]=i;
if (t>x.scf)
{
III y=h.top(); h.pop();
d[y.scsc]=oo;
t-=y.ft;
}
}
for (int i=1; i<=n; i++) {
kq[i].first=d[i];
kq[i].second=i;
}
}
void inkq()
{
int sl=0;
for (int i=1; i<=n; i++)
if (kq[i].first==oo) sl++;
sort(kq+1, kq+1+n);
cout<
cout<
int main()
{
25
