P1873 砍树 40分求调
查看原帖
P1873 砍树 40分求调
1455969
Emma56楼主2024/10/11 13:51

试着写了一个不用二分的题解,然而死活想不出为什么2,3,5,6,9,10号测试点会失败

#include <bits/stdc++.h>
using namespace std;
int N, H, a[1000005]={}, b[400005]={};
long long M;
int main() {
	long long sum=0;
	cin >>N >>M;
	for (int i=1; i<=N; i++) {
		cin >> a[i];
        sum += a[i]; //计算所有树的高度和
		b[a[i]] += 1; //记录每个高度对应的树的数量
	}
	for (int i=1; sum>=M && i<=400000; i++) {
		H=i;
		sum = sum - N; //锯片每调高一米,砍下的总木材减少N
		N = N - b[H]; //当前与锯片同高的树,下一次不会被砍到 
   }
	cout << H-1 << endl;

}

2024/10/11 13:51
加载中...