Sáng kiến kinh nghiệm Lớp các bài toán cơ bản trên mảng một chiều lập trình bằng ngôn ngữ C++

; 
16. tg=di[i]; 
17. di[i]=di[j]; 
18. di[j]=tg; 
19. } 
20. res=0; 
21. for (i=1;ires) res=ti[i]+di[i]; 22. 
else res=res+di[i]; 
23. cout<<res; 
24. return 0; 
25. } 
3. Bài tập chủ đề tìm kiếm trên mảng 
Bài 21. Hướng dẫn: 
Duyệt từ đầu dãy đến cuối dãy, tìm thấy phần tử thỏa mãn là số thân thiện thì 
tăng biến đếm lên một đơn vị. 
Chương trình: 
1. #include 
2. using namespace std; 
3. int a,b,i; 
4. int dao(int n) 
5. { 
6. int t=0; 
7. while (n>0) 
8. { 
60 
9. t=t*10+n%10; 
10. n=n/10; 
11. } 
12. return t; 
13. } 
14. int main() 
15. { 
16. freopen("thanthien.inp","r",stdin); 
17. freopen("thanthien.out","w",stdout); 
18. cin>>a>>b;int d=0; 
19. for (i=a;i<=b;i++) 
20. if (__gcd(i,dao(i))==1) d++; 
21. cout<<d; 
22. } 
Bài 22. Xây hàng rào 
Hướng dẫn: 
Duyệt từ đầu 1 đến n và đếm các a[i] y, chính là số cọc chưa sử 
dụng. 
Chương trình: 
1. #include 
2. using namespace std; 
3. int i,n; 
4. float a[100000002],x,y; 
5. int main() 
6. { 
7. freopen("sococ.inp","r",stdin); 
8. freopen("sococ.out","w",stdout); 
9. cin>>n>>x>>y; 
10. for(i=1;i<=n;i++) 
11. cin>>a[i]; 
12. int d=0; 
13. for(i=1;i<=n;i++) 
14. if((a[i]y)) 
15. d++; 
16. cout<<d; 
17. } 
61 
Bài 23. Số vé 
Hướng dẫn: 
Đọc lần lượt các số x và lưu vào mảng a. Sau đó, kiểm tra nếu a[i] chia hết cho 3 
thì đó là người ngồi ghế hàng 1. Nếu a[i] < 0 và a[i] chia hết cho 2 thì đó là người 
ngồi ghế hàng 2. 
Chương trình: 
1. #include 
2. using namespace std; 
3. int n,x; 
4. int a[100000];int i,d1,d2; 
5. int main() 
6. { 
7. freopen("sove.inp","r",stdin); 
8. freopen("sove.out","w",stdout); 
9. n=0; 
10. while (cin>>x) 
11. { 
12. n++; 
13. a[n]=x; 
14. if (a[n]==0) break; 
15. } 
16. while (a[n]==0) n--; 
17. cout<<n<<endl; 
18. d1=0; d2=0; 
19. for (i=1;i<=n;i++){ 
20. if (a[i] %3==0)d1++; 
21. if ((a[i]<0) && (a[i] % 2==0)) d2++; 22. } 
23. cout<<d1<<endl; 
24. cout<<d2; 
25. return 0; 
26. } 
Bài 24. Số dầu 
Hướng dẫn: 
Tìm vị trí 0 đầu tiên và 0 cuối cùng trong dãy, sau đó tính tổng các số nằm trong 
đoạn vị trí 0 đầu tiên đến vị trí 0 cuối cùng. 
Chương trình: 
62 
1. #include 
2. using namespace std; 
3. float a[50]; 
4. 
5. int n,i,j,k,tong=0; 
6. int vttrdau () 
7. { 
8. int i=1; 
9. while((i<=n)&&(a[i]!=0)) 
10. i++; 
11. return i; 
12. } 
13. int vttrcuoi () 
14. { 
15. int i=n ; 
16. while ((i>=1) &&(a[i]!=0)) 
17. i-- ; 
18. return i ; 
19. } 
20. int main(){ 
21. freopen("sodau.inp","r",stdin); 
22. freopen("sodau.out","w",stdout); 
23. cin>>n; 
24. for (i=1 ;i>a[i]; 
25. tong=0 ; 
26. j=vttrcuoi() ; 
27. i=vttrdau() ; 
28. for (k=i;k<= j ;k++) 
29. tong=tong+a[k] ; 
30. cout << setprecision(2) << fixed << tong; 31. 
return 0; 
32. } 
Bài 25. Patuljci 
Hướng dẫn: 
Tính tổng suma các phần tử trong dãy. Sau đó, kiểm tra (suma - broj[i] - broj[j] = 
100); k khác i và k khác j hay không 
Chương trình: 
1. #include 
2. using namespace std; 
63 
3. int main() { 
4. freopen("patuljci.inp","r",stdin); 
5. freopen("patuljci.out","w",stdout); 
6. int broj[9]; 
7. int suma = 0; 
8. for( int i = 0; i < 9; ++i ) { 
9. cin>>broj[i] ; 
10. suma += broj[i]; 
11. } 
12. for( int i = 0; i < 9; ++i ) 
13. for( int j = i+1; j < 9; ++j ) 
14. if( suma - broj[i] - broj[j] == 100 ) 15. for( 
int k = 0; k < 9; ++k ) 
16. if( k != i && k != j ) 
17. cout<< broj[k] <<endl; 
18. return 0; 
19. } 
Bài 26. Shell Game 
Hướng dẫn: 
Mô phỏng chuyển động của viên sỏi dựa trên ba điểm xuất phát có thể có của nó, 
lấy điểm nào mang lại nhiều câu trả lời đúng nhất. 
Chương trình: 
1. #include 
2. using namespace std; 
3. long long n,a[10000],b[10000],c[10000]; 
4. long long p,dem,kq; 
5. void mo() 
6. { 
7. freopen("shell.inp","r",stdin); 
8. freopen("shell.out","w",stdout); 
9. } 
10. void doc() 
11. { 
12. cin>>n; 
13. for(int i=1;i<=n;i++) 
14. { 
15. cin>>a[i]>>b[i]>>c[i]; 
16. } 
17. } 
18. void xuly() 
64 
19. { 
20. kq=0; 
21. for(int k=1;k<=3;k++) 
22. { 
23. p=k;dem=0; 
24. for(int i=1;i<=n;i++) 
25. { 
26. if(p==a[i]) p=b[i]; 
27. else if(p==b[i]) p=a[i]; 
28. if(c[i]==p) dem++; 
29. } 
30. kq=max(kq,dem); 
31. } 
32. cout<<kq; 
33. } 
34. int main() 
35. { 
36. mo(); 
37. doc(); 
38. xuly(); 
39. } 
Bài 27. Tìm ước 
Hướng dẫn: 
Viết hàm kiểm tra dãy con có độ dài k là ước của dãy A. Sau đó, duyệt từ 1 đến 
n/2 để tìm k. 
Chương trình: 
1. #include 
2. using namespace std; 
3. const int N = 1e4 + 4; 
4. int n; 
5. int a[N]; 
6. bool check(int k) 
7. { 
8. for(int i = 1; i <= n - k; ++i) 
9. if(a[i] != a[i + k]) return false; 
10. return true; 
11. } 
12. int main() 
13. { 
14. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
65 
15. freopen("timuoc.inp","r",stdin); 
16. freopen("timuoc.out","w",stdout); 
17. cin >> n; 
18. for(int i = 1; i > a[i]; 19. 
for(int i = 1; i <= n / 2; ++i) 
20. if(check(i)) {cout << i; return 0;} 21. 
cout << n; 
22. } 
Bài 28. Socola 
Hướng dẫn: 
- Duyệt từ 1 đến n để tính tổng thời gian ti[i] của Tí đã ăn thanh socola. - Duyệt 
từ n trở về 1 để tính tổng thời gian teo[i] của Tèo đã ăn thanh socola. 
- Duyệt từ 1 đến n so sánh ti[i] và teo[i], nếu t[i] < teo[i] thì Tí ăn thêm 1 thanh 
socola ngược lại thì Teo ăn thêm 1 thanh socola. 
Chương trình: 
1. #include 
2. using namespace std; 
3. int n; 
4. int a[100001]; 
5. int ti[100001]; 
6. int teo[100001]; 
7. int main() 
8. { 
9. freopen("socola.inp","r",stdin); 
10. freopen("socola.out","w",stdout); 
11. int d=0; 
12. cin>>n; 
13. for(int i=1;i>a[i]; 
14. ti[1]=a[1]; 
15. teo[n]=a[n]; 
16. for(int i=2;i<=n;i++) ti[i]=ti[i-1]+a[i]; 17. 
for(int i=n-1;i>=1;i--) teo[i]=teo[i+1]+a[i]; 18. 
for(int i=1;i<=n;i++) 
19. { 
20. if(ti[i]<=teo[i]) d++; 
21. else break; 
22. } 
23. cout<<d<<' '<<n-d; 
24. } 
66 
Bài 29. Herding 
Hướng dẫn: 
- Sắp xếp dãy tăng dần 
- Viết hàm tìm tmin, tmax để tìm số lần di chuyển tối thiểu và tối đa. 
Chương trình: 
25. #include 
26. using namespace std; 
27. long long a[3]; 
28. long long tmin(int x,int y,int z) 
29. { 
30. int amin; 
31. if (x + 1 == y && y + 1 == z) amin = 0; 32. else 
if (y - x == 2 || z - y == 2) amin = 1; 33. else 
amin = 2; 
34. return amin; 
35. } 
36. long long tmax(int x,int y,int z) 
37. { 
38. int k=max (y-x,z-y); 
39. return k-1; 
40. } 
41. int main() 
42. { 
43. freopen("herding.inp", "r", stdin); 
44. freopen("herding.out", "w", stdout); 
45. for (int i=1;i>a[i]; 
46. sort(a+1,a+4); 
47. cout<<tmin(a[1],a[2],a[3])<<endl; 
48. cout<<tmax(a[1],a[2],a[3]); 
49. return 0; 
50. } 
Bài 30. Mixing Milk 
Hướng dẫn: 
Có thể mô phỏng từng lần rót một, theo dõi lượng sữa trong mỗi thùng. Ví dụ, 
nếu đổ từ xô 1 vào xô 2, xô 1 có kích thước c1 và xô 2 có kích thước c2. Trước khi 
đổ, xô 1 có m1 đơn vị sữa và xô 2 có đơn vị m2, thì lượng sữa đổ là min (m1, c2 − 
m2). Do đó sau khi đổ, lượng sữa trong thùng 1 là m1 − min (m1, c2 − m2). Và lượng 
sữa trong xô 2 là m2 + min (m1, c2 − m2). Công thức đổ xô 2 vào xô 3 hoặc xô 3 vào 
xô 1 là tương tự. 
67 
Chương trình: 
1. #include 
2. using namespace std; 
3. string s; 
4. int x[5], v[5]; 
5. void pour(int a, int b) 
6. { 
7. int p = min (x[a], (v[b] - x[b])); 
8. x[a] -= p; 
9. x[b] += p; 
10. } 
11. void xl() 
12. { 
13. for (int i = 1; i <= 100; i++) 
14. { 
15. if (i % 3 == 1) pour(1, 2); 
16. if (i % 3 == 2) pour(2, 3); 
17. if (i % 3 == 0) pour(3, 1); 
18. } 
19. cout<<x[1]<<endl;; 
20. cout<<x[2]<<endl; 
21. cout<<x[3]; 
22. } 
23. int main() 
24. { 
25. freopen("mixmilk.inp", "r", stdin); 
26. freopen("mixmilk.out", "w", stdout); 
27. for (int i = 1; i <= 3; i++) 
28. cin >> v[i] >> x[i]; 
29. xl(); 
30. return 0; 
31. } 
Bài 31. New Year and Hurry 
Hướng dẫn: 
Bài này sử dụng công thức tính cấp số cộng và chặt nhị phân để giải quyết 
Chương trình: 
1. #include 
2. using namespace std; 
3. int main() 
68 
4. { 
5. freopen("newyear.inp","r",stdin); 
6. freopen("newyear.out","w",stdout); 
7. int n,k,dau,cuoi,giua, tmp,res; 
8. cin >> n >> k; 
9. int s = 240 - k; 
10. dau=0; 
11. cuoi=n; 
12. while (dau<=cuoi) 
13. { 
14. giua=(dau+cuoi)/2; 
15. tmp = 0.5*giua*(10+(giua-1)*5); 
16. if (tmp<=s) 
17. res=giua; 
18. if (tmp > s) 
19. cuoi=giua-1; 
20. else 
21. dau=giua+1; 
22. } 
23. cout << res; 
24. return 0; 
25. } 
Bài 32. Blackjack 
Hướng dẫn: 
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
log2n 
Chương trình: 
1. #include 
2. using namespace std; 
3. int n,m,a[1000003],dem=0,kq=0; 
4. int tim(int k,int i,int j) 
5. { 
6. int d=i+1,c=j-1,kq=0; 
7. while (d<=c) 
8. { 
9. int g=(d+c)/2; 
10. if (k+a[g]<=m) 
11. { 
12. kq=g; 
13. d=g+1; 
69 
14. } 
15. else c=g-1; 
16. } 
17. return kq; 
18. } 
19. int main() 
20. { 
21. ios::sync_with_stdio(0); 
22. cin.tie(0);cout.tie(0); 
23. freopen("Blackjack.inp","r",stdin); 
24. freopen("Blackjack.out","w",stdout); 
25. cin>>n>>m; 
26. for (int i=1;i>a[i]; 
27. sort(a+1,a+n+1); 
28. for (int i=1;i<=n;i++) 
29. for (int j=i+1;j<=n;j++) 
30. if (a[i]+a[j]<m) 
31. { 
32. int g=tim(a[i]+a[j],i,j); 
33. kq=max(kq,a[i]+a[j]+a[g]); 
34. } 
35. cout<<kq; 
36. } 
Bài 33. Cặp đôi hoàn hảo 
Hướng dẫn: 
- Sắp xếp mảng tăng dần. 
- Áp dụng thuật toán tìm kiếm nhị phân tìm phần tử lớn nhất nhưng nhỏ hơn 
hoặc bằng x. 
- Duyệt từ từ 1 đến số lượng cặp đôi thỏa mãn. 
Chương trình: 
1. #include 
2. using namespace std; 
3. long long a[100002],d,n,res=0; 
4. long long tknp1(long long a[],long long x,long long 
l,long long r) 
5. { 
6. long long d=l,c=r,g,kq=0; 
7. while(d<=c) 
8. { 
70 
9. g=(d+c)/2; 
10. if(a[g]<=x) 
11. { 
12. kq=g; 
13. d=g+1; 
14. } 
15. else c=g-1; 
16. } 
17. return kq; 
18. } 
19. int main() 
20. { 
21. freopen("capdoihh.inp","r",stdin); 
22. freopen("capdoihh.out","w",stdout); 
23. cin>>n>>d; 
24. for(int i=1;i>a[i]; 
25. sort(a+1,a+n+1); 
26. for(int i=1;i<=n;i++) 
27. { 
28. res+=tknp1(a,a[i]+d,i,n)-i; 
29. cout<<a[i]<<endl; 
30. } 
31. cout<<res; 
32. return 0; 
33. } 
Bài 34. Xếp trứng 
Hướng dẫn: 
Gọi S là tổng các ai, Min là giá trị ai nhỏ nhất, vậy kết quả bài toán nằm trong 
đoạn [Min ... S]. Dãy ai được chọn phải theo thứ tự, với mỗi giá trị của phép chặt nhị 
phân ta kiểm tra xem có thể xếp vào đúng M thùng được không. Chương trình: 
1. #include 
2. using namespace std; 
3. int kq,n,m,a[100005],s,Min; 
4. bool check(int k) 
5. { 
6. int s=0,dem=1; 
7. for(int i=1;i<=n;i++) 
8. { 
9. if(s+a[i]<=k) s+=a[i]; 
10. else 
71 
11. { 
12. if(a[i]>k) return false; 
13. dem++; 
14. if(dem>m) return false; 
15. s=a[i]; 
16. } 
17. } 
18. return true; 
19. } 
20. int main() 
21. { 
22. freopen("xeptrung.inp","r",stdin); 
23. freopen("xeptrung.out","w",stdout); 
24. cin>>n>>m; 
25. for(int i=1;i<=n;i++) 
26. { 
27. cin>>a[i]; 
28. s+=a[i]; 
29. Min=min(Min,a[i]); 
30. } 
31. int d=Min,c=s,g; 
32. while(d<=c) 
33. { 
34. g=(d+c)/2; 
35. if(check(g)) 
36. { 
37. kq=g; 
38. c=g-1; 
39. } 
40. else d=g+1; 
41. } 
42. cout<<kq; 
43. } 
Bài 35. Hàng cây 
Hướng dẫn: 
- Cách 1: Thuật toán vét cạn thử tất cả các độ cao từ cây cao nhất (maxH) tới 0. 
Với mỗi độ cao H, tính tổng số mét gỗ thu được, nếu tổng lớn hơn bằng M đầu tiên ta 
thu được độ cao cần tìm (đây là cách không đạt điểm tối đa). 
- Cách 2: Ta có nhận xét, nếu cắt ở độ cao H lấy được M mét gỗ thì khi cắt độ 
cao H- 1 cũng lấy được M mét gỗ. Ngược lại, nếu cắt ở độ cao H không lấy được M 
72 
mét gỗ thì khi cắt độ cao H+1 cũng không lấy được M mét gỗ. Từ nhận xét trên ta có 
thể sử dụng giải thuật tìm kiếm nhị phân để tìm độ cao H cao nhất cần cắt để lấy được 
M mét gỗ thỏa mãn yêu cầu bài. 
Chương trình: 
1. #include 
2. using namespace std; 
3. int n,a[1000005]; 
4. long long m; 
5. bool check(long long t) 
6. { 
7. long long kq=0; 
8. for(int i=1;i<=n;i++) 
9. if(a[i]>t) kq+=a[i]-t; 
10. if(kq>=m) return true; 
11. return false; 
12. } 
13. int tim(long long m) 
14. { 
15. int d=0,c=a[n],g,kq; 
16. while(d<=c) 
17. { 
18. g=(d+c)/2; 
19. if(check(g)) 
20. { 
21. kq=g; 
22. d=g+1; 
23. } 
24. else c=g-1; 
25. } 
26. return kq; 
27. } 
28. int main() 
29. { 
30. freopen("wood.inp","r",stdin); 
31. freopen("wood.out","w",stdout); 
32. ios::sync_with_stdio(0); 
33. cin.tie(0); 
34. cin>>n>>m; 
35. for(int i=1;i<=n;i++) 
36. cin>>a[i]; 
37. sort(a+1,a+n+1); 
73 
38. cout<<tim(m); 
39. } 
Bài 36. Wires 
Hướng dẫn: 
Ta thử lần lượt độ dài m, sau đó kiểm tra xem có cắt được K đoạn có độ dài m 
không? 
Chương trình: 
1. #include 
2. using namespace std; 
3. int n,k,ma=0,mi=1,kq=0,a[1000003]; 
4. bool kt(int m){ 
5. int d=0; 
6. for (int i=1;i<=n;i++) d+=a[i]/m; 
7. if (d>=k) return true; 
8. return false; 
9. } 
10. int main(){ 
11. ios::sync_with_stdio(0); 
12. cin.tie(0);cout.tie(0); 
13. freopen("wires.inp","r",stdin); 
14. freopen("wires.out","w",stdout); 
15. cin>>n>>k; 
16. for (int i=1;i<=n;i++) 
17. { 
18. cin>>a[i]; 
19. ma=max(ma,a[i]); 
20. } 
21. while (mi<=ma) 
22. { 
23. int g=(mi+ma)/2; 
24. if (kt(g)) 
25. { 
26. kq=g; 
27. mi=g+1; 
28. } 
29. else ma=g-1; 
30. } 
31. cout<<kq; 
32. } 
74 
Bài 37. Jump 
Hướng dẫn: 
- Gọi T[i] là phần tử nhỏ nhất từ a1 đến ai. Vậy T là dãy giảm dần. 
- Duyệt tất cả các chỉ số j từ 1 đến N. Với mỗi j ta tìm kiếm nhị phân trên trên 
đoạn chỉ số [1, j-1] của dãy T phần tử lớn nhất thỏa mãn ≤ a[j]-p. 
Chương trình: 
1. #include 
2. using namespace std; 
3. const int maxn=100000; 
4. int a[maxn],t[maxn],n,p,kq,i,j; 
5. int tknp(int l,int h) 
6. { 
7. int tg,dau,cuoi,giua; 
8. tg=h; 
9. dau=1; 
10. cuoi=h-1; 
11. while (dau<=cuoi) 
12. { 
13. giua=(dau+cuoi) / 2; 
14. if (t[giua]<=a[h]-p) 
15. { 
16. tg=giua; 
17. cuoi=giua-1; 
18. } 
19. else dau=giua+1; 
20. } 
21. return tg; 
22. } 
23. int main () 
24. { 
25. freopen("jump.inp","r",stdin); 
26. freopen("jump.out","w",stdout); 
27. cin>>n>>p; 
28. for (i=1;i>a[i]; 
29. t[1]=a[1]; 
30. for (i=2;i<=n;i++) 
31. t[i]=min(t[i-1],a[i]); 
32. kq=0; 
33. for (i=2;i<=n;i++) 
34. { 
75 
35. j=tknp(1,i); 
36. if (i-j>kq) kq=i-j; 
37. } 
38. 
39. cout<<kq; 
40. return 0; 
41. } 
Bài 38. Dãy số 
Hướng dẫn: 
- Trước hết tính tổng các số từ 1 đến n và lưu vào mảng f - 
Sắp xếp mảng f 
- Áp dụng thuật toán tìm kiếm nhị phân để tìm số cặp (i, j) 
Chương trình: 
1. #include 
2. using namespace std; 
3. long long res,n,l,r,a[100005],d,c,k,g,l1,r1; 
4. long long f[100005]; 
5. int main() 
6. { 
7. memset(f,0,sizeof(f)); 
8. freopen("seq.inp","r",stdin); 9. 
freopen("seq.out","w",stdout); 10. 
cin>>n>>l>>r; 
11. for(int i=1;i<=n;i++) 
12. cin>>a[i]; 
13. f[0]=0; 
14. f[1]=a[1]; 
15. for(int i=2;i<=n;i++) 
16. { 
17. f[i]=f[i-1]+a[i]; 
18. } 
19. sort(f,f+n+1); 
20. for(int i=1;i<=n;i++) 
21. { 
22. l1=i-1;r1=0; 
23. d=0;c=i-1; 
24. while(d<=c) 
25. { 
26. g=(d+c)/2; 
76 
27. if(f[i]-f[g]<l) 
28. { 
29. c=g-1; 
30. l1=g-1; 
31. } 
32. else d=g+1; 
33. } 
34. d=0;c=i-1; 
35. while(d<=c) 
36. { 
37. g=(d+c)/2; 
38. if(f[i]-f[g]>r) 
39. { 
40. d=g+1; 
41. r1=g+1; 
42. } 
43. else c=g-1; 
44. } 
45. if(l1 >= r1) res+=l1-r1+1; 
46. } 
47. cout<<res; 
48. } 
Bài 39. Cho thuê máy 
Hướng dẫn: 
- Sắp xếp mảng a, b bằng thuật toán quicksort. 
- Dùng thuật toán tìm kiếm nhị phân để tìm tổng thời gian thực hiện lớn nhất. 
Chương trình: 
1. #include 
2. using namespace std; 
3. long long i,j,n,a[1000000],b[1000000],k[1000000],mx; 
4. long long np(long long x,long long y) 
5. { 
6. long long res=0; 
7. long long l=x,r=y; 
8. while(l<=r) 
9. { 
10. long long g=(l+r)/2; 
11. if(b[g]<=a[y]) {res=g;l=g+1;} 
12. else r=g-1; 
13. } 
14. return res; 
77 
15. } 
16. void quicksort(long long a[],long long b[],long long 
l,long long r) 
17. { 
18. i=l;j=r; 
19. long long x=a[(l+r)/2]; 
20. do 
21. { 
22. while(a[i]<x)i++; 
23. while(a[j]>x) j--; 
24. if(i<=j) 
25. { 
26. swap(a[i],a[j]); 
27. swap(b[i],b[j]); 
28. i++;j--; 
29. } 
30. } 
31. while(i<=j); 
32. if(l<j) quicksort(a,b,l,j); 
33. if(i<r) quicksort(a,b,i,r); 
34. } 
35. int main() 
36. { 
37. freopen("max.inp","r",stdin); 
38. freopen("max.out","w",stdout); 
39. cin>>n; 
40. k[0]=0; 
41. for(int i=1;i<=n;i++) 
42. cin>>a[i]>>b[i]; 
43. quicksort(b,a,1,n); 
44. k[1]=b[1]-a[1]; 
45. mx=k[1]; 
46. for(int i=2;i<=n;i++) 
47. { 
48. k[i]=b[i]-a[i]+k[np(1,i)]; 
49. mx=k[i]=max(k[i],mx); 
50. } 
51. cout<<mx; 
52. return 0; 
53. } 
78 
Bài 40. Làm gốm 
Hướng dẫn: Nhận xét rằng tất cả các sản phẩm đều phải nặn xong mới chuyển 
sang vẽ do vậy trong ngày làm việc khoảng thời gian đầu, công nhân xưởng vẽ được 
nghỉ và khoảng thời gian sau, công nhân xưởng nặn được nghỉ. 
Đặt S là khoảng thời gian làm việc của công nhân xưởng nặn. Khi đó khoảng 
thời gian làm việc của công nhân xưởng vẽ là T-S. 
Với thời gian S, xưởng nặn làm được tối đa là: 
      
S S S 
f(S)= 
    
+ + +  
 
     
sản phẩm 
... 
a a a 
1 2 n 
và với thời gian T-S thì xưởng vẽ làm được tối đa: 
      − − − 
T S T S T S 
    
+ + +   
     
sản phẩm
g(S)= 
... 
b b b 
1 2 
m 
Điều kiện để số sản phẩm được hoàn thành hết trong ngày là h(S)=g(S)-f(S)≥0. 
Nhận xét rằng hàm h(S) là hàm đơn điệu giảm theo S. Hơn nữa nếu S càng lớn thì số 
sản phẩm làm ra được càng nhiều (bằng f(S)). Do vậy ta có thể sử dụng tìm kiếm nhị 
phân để tìm thời điểm lớn nhất S mà h(S)≥0. 
Sau khi tìm được S, giá trị cần tìm là f(S) 
Chương trình : 
1. #include 
2. #define int long long 
3. using namespace std; 
4. int a[100005], t, m, n, s, b[100005]; 
5. int g(int x) 
6. { 
7. int i, kq; 
8. kq = 0; 
9. for (i = 1; i<= m; i++) kq = kq + x/b[i]; 10. 
return kq; 
11. } 
12. int f(int x) 
13. { 
14. int i, kq; 
15. kq = 0; 
16. for (i = 1; i<= n; i++) kq = kq + x/a[i]; 17. 
return kq; 
18. } 
19. main() 
79 
20. { 
21. freopen("pottery.inp", "r", stdin); 
22. freopen("pottery.out", "w", stdout); 
23. cin >> t >> n; 
24. for(int i = 1; i > a[i]; 25. 
cin >> m; 
26. for(int i = 1; i > b[i]; 27. 
int lo, hi, mid; 
28. if (g(0)-f(t)>=0) 
29. { 
30. s = t; 
31. return 0; 
32. } 
33. lo = 0; hi = t; 
34. do 
35. { 
36. mid =(lo+hi) / 2; 
37. if (g(t - mid)-f(mid) >= 0) lo = mid; 38. else 
hi = mid; 
39. } 
40. while (hi-lo != 1); 
41. s = lo; 
42. cout << f(s); 
43. } 
4. Bài tập chủ đề tìm đoạn con dài nhất thỏa mãn điều kiện cho trước. 
Bài 41. Tìm dãy con đơn điệu 
Hướng dẫn: 
Duyệt từ i bằng 2 đến n và kiểm tra nếu a[i] <= a[i-1] thì cập nhật lại đoạn mới, 
ngược lại độ dài đoạn con tăng lên 1. Độ dài đoạn con cần tìm là max độ dài của các 
đoạn con. 
Chương trình: 
1. #include 
2. using namespace std; 
3. int n,i, len=1, maxlen=1; 
4. int a[100000]; 
5. int main () 
6. { 
7. freopen ("dondieutang.inp", "r", stdin); 8. 
freopen ("dondieutang.out", "w", stdout); 
80