题目
要砍M米长木材，需找到伐木机锯片的最大整数高度H，保证能得到至少M米木材，锯掉树比H高的部分，得到锯下部分木材，且再升高1米就得不到M米木材
1≤N≤106，1≤M≤2×10e9，树的高度 ≤4×10e5 ，所有树的高度总和 >M
INPUT
第 1 行 2 个整数 N 和 M，N表示树木的数量，M表示需要的木材总长度
第 2 行 N 个整数表示每棵树的高度
OUTPUT
1 个整数，表示锯片的最高高度
Example Input
4 7
20 15 10 17
5 20
4 42 40 26 46
Example Output
15
36
+++
[!TIP]
利用二分查找 在每次循环中，计算中间值mid（锯片高度）然后遍历所有树木，对高于mid的树计算锯下部分的长度并累加得到 sum再根据 sum与M的比较结果来调整查找范围
时间复杂度：O（nlog）
[!WARNING]
二分查找使用int mid = (baka + maxh) / 2;可能会溢出，不能确保向上取整或死循环，应该用int mid = maxh + (baka - maxh + 1) / 2;来避免类似情况发生
| 用时 | 内存 |
|---|---|
| 385ms | 4.23MB |
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
int n, m;
scanf("%d %d", &n, &m);//更快
vector<int> tree(n);
//或者int tree[1145141];
for (int i = 0; i < n; i++)
{
scanf("%d", &tree[i]);
}
int maxh = 0;
int baka = 11451419;
//二分找合适高度
while (maxh < baka)//（即left < right）
{
int mid = maxh + (baka - maxh + 1) / 2;
//避免整数溢出和死循环
long long sum = 0;
// 计算剩树高度和
for (int i = 0; i < n; i++)
{
if (tree[i] > mid)
{
sum += tree[i] - mid;
}
}
if (sum >= m)
{
maxh = mid;
}
else
{
baka = mid - 1;
}
}
printf("%d\n", maxh);
return 0;
}
[!TIP]
同时可以用algorithm（max）预处理最大值减少二分查找范围，提高效率
| 用时 | 内存 |
|---|---|
| 370ms | 4.22MB |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
scanf("%d %d", &n, &m);
vector<int> tree(n);
int fumo = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &tree[i]);
fumo = max(fumo, tree[i]);
}
int maxh = 0;
int baka = fumo;
while (maxh < baka)
{
int mid = maxh + (baka - maxh + 1) / 2;
long long sum = 0;
for (int i = 0; i < n; i++)
{
if (tree[i] > mid)
{
sum += tree[i] - mid;
}
}
if (sum >= m)
{
maxh = mid;
}
else
{
baka = mid - 1;
}
}
printf("%d\n", maxh);
return 0;
}
[!TIP]
在题解里看到一个用sort排序再从后往前查找的方法，这里做一下记录
假设已砍过了i棵树（树由高到低排），那此时被砍过的i棵树的高度均等于第i+1棵树的高度
再砍一棵树（砍第i+1棵）后获得的新高度为（第i+1棵树的高度-第i+2棵树的高度）
*（i+1）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tree[1000001];
int n, m;
int main() {
int i, num, ans;
long long sum;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++) {
scanf("%d", &tree[i]);
}
// 对树的高度进行升序排序
sort(tree + 1, tree + n + 1);
sum = 0;
num = n;
// 计算累计的剩余树木总高度，直到超过m
while (sum < m) {
sum += (tree[num] - tree[num - 1]) * (n - num + 1);
num--;
}
num++;
ans = tree[num - 1] + (sum - m) / (n - num + 1);
printf("%d\n", ans);
return 0;
}
[!TIP]
还有面向结果编程艹
#include<cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if(n==10) printf("23");
if(n==750444) printf("10662");
if(n==999888) printf("7994");
if(n==300) printf("114");
if(n==1000) printf("3961");
if(n==10000) printf("70");
if(n==30000) printf("237704");
if(n==100000) printf("86792");
if(n==300001) printf("47429");
if(n==555444) printf("19879");
}