二分答案
![]()
#include <stdio.h> #include <stdlib.h> #define MAX_N 105 int n, k; int h[MAX_N]; // 检查高度为 height 时，能否切出至少 k 件产品 int check(int height) { if (height == 0) return 0; // 避免除零 int total = 0; for (int i = 0; i < n; i++) { total += h[i] / height; } return total >= k; } int main() { scanf("%d %d", &n, &k); int max_h = 0; long long sum = 0; // 用于判断是否连高度1都达不到 for (int i = 0; i < n; i++) { scanf("%d", &h[i]); if (h[i] > max_h) max_h = h[i]; sum += h[i]; } // 特殊情况：即使高度为1，也无法切出k件 if (sum < k) { printf("-1\n"); return 0; } // 二分答案 int left = 1, right = max_h; int ans = 1; // 至少可以切出高度1的产品（已排除sum<k的情况） while (left <= right) { int mid = left + (right - left) / 2; if (check(mid)) { ans = mid; // 记录当前可行解 left = mid + 1; // 尝试更高的高度 } else { right = mid - 1; } } printf("%d\n", ans); return 0; }
二分答案 + 贪心验证（最大化最小值）
![]()
#include <stdio.h> #include <stdlib.h> #define MAX_N 100005 int n, m; int x[MAX_N]; int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int check(int dist) { int count = 1; int last_pos = x[0]; for (int i = 1; i < n; i++) { if (x[i] - last_pos >= dist) { count++; last_pos = x[i]; if (count >= m) return 1; } } return count >= m; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &x[i]); } qsort(x, n, sizeof(int), cmp); int left = 0, right = x[n-1] - x[0]; int ans = 0; while (left <= right) { int mid = left + (right - left) / 2; if (check(mid)) { ans = mid; left = mid + 1; } else { right = mid - 1; } } printf("%d\n", ans); return 0; }
数学优化 + 枚举/二分查找
![]()
#include <stdio.h> // 计算一个数的十进制位数 int get_digits(long long n) { if (n == 0) return 1; int count = 0; while (n > 0) { n /= 10; count++; } return count; } int main() { long long A, B, X; if (scanf("%lld %lld %lld", &A, &B, &X) != 3) { return 0; } long long left = 1; long long right = 1000000000LL; // 10^9 long long ans = 0; // 记录最大可行的 N，初始为 0 表示没找到 while (left <= right) { long long mid = left + (right - left) / 2; // 计算当前 mid 的价格 int len = get_digits(mid); // 注意：这里可能会溢出吗？ // A <= 10^9, mid <= 10^9 -> A*mid <= 10^18 (long long 最大值约 9*10^18)，安全 // B <= 10^9, len <= 10 -> B*len <= 10^10，安全 long long cost = A * mid + B * len; if (cost <= X) { // 钱够，可以尝试买更大编号的海鲜 ans = mid; // 记录当前可行解 left = mid + 1; // 向右搜索 } else { // 钱不够，必须买小编号的 right = mid - 1; // 向左搜索 } } printf("%lld\n", ans); return 0; }
贪心思想+二分答案
![]()
#include <stdio.h> #include <stdlib.h> int n; long long m, k; long long a[1005]; int cmp(const void *a, const void *b) { long long val1 = *(const long long *)a; long long val2 = *(const long long *)b; if (val1 < val2) return -1; if (val1 > val2) return 1; return 0; } int check(long long x) { int op = 0; for (int i = n / 2; i < n; i++) { if (a[i] < x) { // 如果需要修改，先检查加了 k 够不够 if (a[i] + k < x) { return 0; // 即使加了 k 也达不到 x，失败 } op++; // <--- 只有真正需要修改时，操作数才 +1 } // 如果 a[i] >= x，不需要操作，op 不变 // 优化：如果中途操作数已经超过 m，直接返回失败 if (op > m) { return 0; } } return 1; } int main() { if (scanf("%d %lld %lld", &n, &m, &k) != 3) { return 0; } for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); } qsort(a, n, sizeof(long long), cmp); long long left = a[n / 2]; long long right = 2000000000000000000LL; // 2e18 long long ans = left; while (left <= right) { long long mid = left + (right - left) / 2; if (check(mid)) { ans = mid; left = mid + 1; } else { right = mid - 1; } } printf("%lld\n", ans); return 0; }
