洛谷 P1873. 砍树 二分
原题链接
简单
作者:
中国鲜果茶
,
2022-02-16 15:15:45
,
所有人可见
,
阅读 180
不开long long会爆
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, k;
// 计算当前收益
int get(int x)
{
int res = 0;
for(int i = 0; i < n; ++ i)
if(a[i] > x) res += a[i] - x;
return res;
}
int bsearch(int x)
{
int l = 0, r = a[n - 1];
while(l < r)
{
int mid = l + r + 1 >> 1;
if(get(mid) >= x) l = mid; // 砍的太多了,可以是可以,最好要砍低一点,先保留
else r = mid - 1; // 砍得太少,根本不够,一定要再多砍一点
}
return l;
}
signed main()
{
cin >> n >> k;
for(int i = 0; i < n; ++ i) scanf("%d", &a[i]);
sort(a, a + n);
cout << bsearch(k);
return 0;
}
后来发现 其实排不排序无所谓,因为我们二分的是0-最高的数的高度之间的距离,并不是二分每一棵树
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, k;
int toppest = -1;
int get(int x)
{
int res = 0;
for(int i = 0; i < n; ++ i)
if(a[i] > x) res += a[i] - x;
return res;
}
int bsearch(int x)
{
int l = 0, r = toppest;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(get(mid) >= x) l = mid; // 砍的太多了,可以是可以,最好要砍低一点,先保留
else r = mid - 1; // 砍得太少,根本不够,一定要再多砍一点
}
return l;
}
signed main()
{
cin >> n >> k;
for(int i = 0; i < n; ++ i) scanf("%d", &a[i]), toppest = max(toppest, a[i]);
cout << bsearch(k);
return 0;
}