二分查找与深度优先搜索算法应用解析
二分查找边界定位实现
在有序序列中定位目标值的首次出现位置，需处理边界条件。数组容量不足是常见错误，需根据数据规模合理分配内存。关键逻辑在于当中间值等于目标时，继续向左边界搜索以定位首次出现位置。
#include <iostream>
#include <climits>
using namespace std;
const int MAXN = 1000007;
int data[MAXN];
int binary_first(int target, int size) {
int left = 0, right = size + 1;
data[0] = INT_MIN;
data[size + 1] = INT_MAX;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (data[mid] >= target) right = mid;
else left = mid;
}
return data[right] == target ? right : -1;
}
int main() {
int n, q, val;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> data[i];
while (q--) {
cin >> val;
cout << binary_first(val, n) << ' ';
}
return 0;
}深度优先搜索实现全排列
经典排列问题通过递归回溯实现。使用访问标记数组防止元素重复使用，当路径长度达到元素总数时输出当前排列。注意输出格式要求固定宽度对齐。
#include <iomanip>
#include <vector>
using namespace std;
vector<int> path;
vector<bool> visited;
void dfs_permute(int current, int total) {
if (current > total) {
for (int num : path) cout << setw(5) << num;
cout << '\n';
return;
}
for (int i = 1; i <= total; i++) {
if (!visited[i]) {
visited[i] = true;
path.push_back(i);
dfs_permute(current + 1, total);
path.pop_back();
visited[i] = false;
}
}
}
int main() {
int n;
cin >> n;
visited.resize(n + 1, false);
dfs_permute(1, n);
return 0;
}巧克力分割的二分求解
通过二分法确定最大切割边长。验证函数计算给定尺寸可分割的巧克力总数，需注意面积计算应为长宽可分割数量的乘积而非加和。切割尺寸与可分割数量呈反比关系。
#include <algorithm>
using namespace std;
bool validate(int size, int rows[], int cols[], int count, int need) {
long total = 0;
for (int i = 0; i < count; i++) {
total += static_cast<long>(rows[i]/size) * (cols[i]/size);
if (total >= need) return true;
}
return false;
}
int main() {
int n, k, max_dim = 0;
cin >> n >> k;
int heights[n], widths[n];
for (int i = 0; i < n; i++) {
cin >> heights[i] >> widths[i];
max_dim = max(max_dim, max(heights[i], widths[i]));
}
int low = 0, high = max_dim + 1;
while (low + 1 < high) {
int mid = (low + high) / 2;
validate(mid, heights, widths, n, k) ? low = mid : high = mid;
}
cout << low << endl;
return 0;
}木材切割的二分应用
典型二分答案问题。切割长度与可获得段数成反比，验证函数计算当前长度下可获得的木材段数。特别处理输入为零的边界情况。
bool check_cut(int len, int logs[], int count, int need) {
if (len == 0) return false;
long segments = 0;
for (int i = 0; i < count; i++) {
segments += logs[i] / len;
if (segments >= need) return true;
}
return false;
}
int main() {
int n, k;
cin >> n >> k;
int timber[n], max_len = 0;
for (int i = 0; i < n; i++) {
cin >> timber[i];
max_len = max(max_len, timber[i]);
}
int left = 0, right = max_len + 1;
while (left + 1 < right) {
int mid = (left + right) / 2;
check_cut(mid, timber, n, k) ? left = mid : right = mid;
}
cout << left << endl;
return 0;
}猫粮规划的剪枝优化
组合问题使用DFS遍历所有可能子集。通过排序预处理和当前和判断实现剪枝：当累计值超过上限时终止当前分支搜索，显著提升效率。
#include <algorithm>
using namespace std;
int count_subsets(int nums[], int idx, int total, int n, int low, int high) {
int valid = (total >= low && total <= high) ? 1 : 0;
if (total > high || idx >= n) return valid;
for (int i = idx; i < n; i++)
valid += count_subsets(nums, i + 1, total + nums[i], n, low, high);
return valid;
}
int main() {
int n, low_bound, up_bound;
cin >> n >> low_bound >> up_bound;
int portions[n];
for (int i = 0; i < n; i++) cin >> portions[i];
sort(portions, portions + n);
cout << count_subsets(portions, 0, 0, n, low_bound, up_bound) << endl;
return 0;
}K皇后攻击范围标记法
使用四个标记数组分别处理行、列、主副对角线。避免二维数组遍历，通过数学关系直接计算对角线标识。被标记位置即为可攻击区域。
int main() {
int rows, cols, queens;
cin >> rows >> cols >> queens;
bool row_mark[rows+1] = {0}, col_mark[cols+1] = {0};
bool diag1[rows+cols+1] = {0}, diag2[rows+cols+1] = {0};
while (queens--) {
int r, c;
cin >> r >> c;
row_mark[r] = col_mark[c] = true;
diag1[r + c] = diag2[rows + r - c] = true;
}
int safe_count = 0;
for (int r = 1; r <= rows; r++) {
if (row_mark[r]) continue;
for (int c = 1; c <= cols; c++) {
if (!col_mark[c] && !diag1[r+c] && !diag2[rows+r-c])
safe_count++;
}
}
cout << safe_count;
return 0;
}路标设置的二分答案
空旷指数与需添加路标数量成反比。验证函数计算当前空旷指数下需要补充的路标总数，通过相邻路标间距计算需插入的数量。采用左开右闭二分搜索确定最小值。
bool check_gaps(int gap, int markers[], int count, int total_len, int max_add) {
long need = 0;
need += (markers[0] - 1) / gap;
for (int i = 1; i < count; i++)
need += (markers[i] - markers[i-1] - 1) / gap;
need += (total_len - markers[count-1] - 1) / gap;
return need <= max_add;
}
int main() {
int length, existing, additions;
cin >> length >> existing >> additions;
int positions[existing];
for (int i = 0; i < existing; i++) cin >> positions[i];
int low = 0, high = length;
while (low + 1 < high) {
int mid = (low + high) / 2;
check_gaps(mid, positions, existing, length, additions) ? high = mid : low = mid;
}
cout << high;
return 0;
}设备供电的浮点二分
设备运行时间与所需充电量成正比。验证函数计算总运行时间下充电宝需补充的能量总和，注意浮点数精度处理。特判无限运行的情况。
#include <cmath>
const double EPS = 1e-5;
bool check_runtime(double time, double consume[], double battery[], int n, double power) {
double required = 0;
for (int i = 0; i < n; i++) {
double need = consume[i] * time;
if (need > battery[i]) required += need - battery[i];
}
return required <= power * time;
}
int main() {
int devices;
double power;
cin >> devices >> power;
double consume[devices], battery[devices];
for (int i = 0; i < devices; i++) cin >> consume[i] >> battery[i];
double low = 0, high = 1e10;
while (high - low > EPS) {
double mid = (low + high) / 2;
check_runtime(mid, consume, battery, devices, power) ? low = mid : high = mid;
}
fabs(high - 1e10) < EPS ? cout << "-1" : cout << low;
return 0;
}