Bài A: Tối Ưu Hóa Chèn Chữ Số
Phân tích cho thấy nên đặt chữ số lớn nhất có thể ở vị trí cao nhất. Thuật toán duyệt chuỗi từ trái sang phải, chèn chữ số mới trước chữ số đầu tiên nhỏ hơn nó. Sử dụng phương thức insert() của lớp std::string để thực hiện thao tác này hiệu quả:
str.insert(pos, char_count, character): Chèncharacterlặpchar_countlần tại vị tríposstr.insert(pos, substring): Chèn chuỗi con vào trước vị trípos
Nếu không tìm thấy vị trí chèn phù hợp, thêm chữ số vào cuối chuỗi.
Xem mã nguồn
#include <iostream>
#include <string>
using namespace std;
void processTestCase() {
int length, digit;
cin >> length >> digit;
string numStr;
cin >> numStr;
string newDigit = to_string(digit);
bool inserted = false;
for (size_t idx = 0; idx < numStr.size(); ++idx) {
if (digit > numStr[idx] - '0') {
numStr.insert(idx, newDigit);
inserted = true;
break;
}
}
cout << (inserted ? numStr : numStr + newDigit) << '\n';
}
int main() {
int cases;
cin >> cases;
while (cases--) processTestCase();
return 0;
}Bài B: Tính Toán Đường Đi Tối Ưu Trên Lưới
Bài toán yêu cầu tìm số bước di chuyển tối thiểu giữa hai điểm trên lưới vuông. Quan sát thấy khoảng cách tới biên lưới quyết định lớp (ring) của điểm. Công thức tính lớp của điểm (x,y) trên lưới kích thước N×N:
layer = min(x-1, y-1, N-x, N-y)
Chênh lệch lớp giữa hai điểm chính là số bước di chuyển tối thiểu cần tìm.
Xem mã nguồn
#include <iostream>
#include <algorithm>
using namespace std;
int calculateLayer(int x, int y, int size) {
return min({x-1, y-1, size-x, size-y});
}
void solveGridProblem() {
int gridSize, x1, y1, x2, y2;
cin >> gridSize >> x1 >> y1 >> x2 >> y2;
int startLayer = calculateLayer(x1, y1, gridSize);
int endLayer = calculateLayer(x2, y2, gridSize);
cout << abs(startLayer - endLayer) << '\n';
}
int main() {
int tests;
cin >> tests;
while (tests--) solveGridProblem();
return 0;
}Bài C: Xây Dựng Mảng Với Ràng Buộc Tối Ưu
Yêu cầu xây dựng mảng A từ mảng B sao cho max(A[i], A[i+1]) = B[i]. Chiến lược tham lam:
- Khởi tạo mảng kết quả với giá trị mặc định
- Với mỗi vị trí i, đặt
A[i] = B[i]vàA[i+1] = 0làm giá trị tạm - Kiểm tra điều kiện với phần tử trước: nếu
max(B[i], A[i-1])vượt quáB[i-1], điều chỉnh bằng cách gánA[i] = B[i]
Quyết định này đảm bảo không vi phạm ràng buộc với các phần tử đã xử lý trước đó.
Xem mã nguồn
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
void constructArray() {
int n;
cin >> n;
vector<int> inputB(n-1);
for (int i = 0; i < n-1; ++i) cin >> inputB[i];
vector<int> result(n, 0);
result[0] = inputB[0];
for (int i = 1; i < n-1; ++i) {
if (max(inputB[i], result[i-1]) == inputB[i-1]) {
result[i] = inputB[i];
} else {
result[i+1] = inputB[i];
}
}
for (int val : result) cout << val << ' ';
cout << '\n';
}
int main() {
int cases;
cin >> cases;
while (cases--) constructArray();
return 0;
}