前缀和算法

前缀和算法在处理加和问题时能有效降低时间复杂度，~~乃居家常备法宝~~

~~你想打暴力当然也可以~~

这个算法的思路就是，遍历到第n个数，就把他前面的加起来

类似数学上的数列求和吧

Sn=Sn-1+an//打不出来下标，凑活看吧

代码实现

for(int i=1;i<=n;i++)
    cin>>a[i];
for(int i=1;i<=n;i++)
    dp[i]=dp[i-1]+a[i];

就这样，直白如话，通俗易懂！

这样看，他确实降低了计算量，每次只需要计算两个加和诶！

如果想要取[l,r]范围内的和

dp[r] - dp[l-1]

很简单的

二分查找

就是对一串数对半搜索

搜不到，砍一半，在半个区间再找，循环往复

看到别人一个写的很好的，直接把他的博客引一下吧

https://blog.csdn.net/2302_79577794/article/details/139581587

对于有重复数据情况

2025.4.6

对于有重复数据的情况，一般让求第一次或最后一次出现的位置，以第一次为例循环条件设置为l<r

作为有序数列，越靠前数字越小，查找第一次出现的位置，我们要尽量向左收缩

即num<=a[mid]时r=mid 区别在于是小于等于而不是小于，else l=mid+1

为什么r=mid而不是r=mid-1呢？我的理解是右指针r向左收缩，而我们要去找尽量靠左（第一次出现的位置）如果是mid-1，就很有可能错过mid就是当前所要求的位置的情况，那为什么mid就可能是所要求的位置呢

因为之前说到尽量向左收缩num<=a[mid] 这里有个等于号，匹配（不一定是所求）的位置都被更新到右指针r中了所以r=mid与num<=a[mid]是相辅相成的

找最后一次出现的位置同理，num>=a[mid]; l=mid else r=mid-1 但这里要注意mid=(l+r+1)/2 要多加1

具体原因看上面贴的博客，讲的灰常好~

7-4 砍树取暖

全屏浏览

切换布局

作者 zyc

单位山东科技大学

砍树取暖
到冬天了，小Z想要取暖，但小Z所在的地区只可以用木材取暖，因此他需要获取长度为k的木材，他家附近有一排树有n棵，同时他有一个伐木机可以设置锯片的高度H(即树高于H的部分会被砍掉)，但是电锯的高度改变很麻烦，并且伐木机必须从第一棵树走到最后一棵树(砍高于H的部分)，因此他希望在电锯不调节高度的前提下，进行砍树。小Z不想浪费，因此砍下来的木材的总长度要尽可能等于k(即再升高一米锯子就不够k了)

输入格式:

第1行有两个正整数n k，n表示树木的数量，k表示需要的木材的总长度（1≤n≤10^6^，1≤k≤2*10^9^）
第2行有n个正整数，表示第i棵树的高度ai（1≤ai≤4×10^5^且所有树的高度总和>k）

输出格式:

输出锯片的高度

输入样例:

在这里给出一组输入。例如：

1 2	8 15 10 12 5 3 4 8 2 9

输出样例:

在这里给出相应的输出。例如：

题解：

#include<bits/stdc++.h>
using namespace std;
long long gt(const vector<int>& trees,int H)//传vector数组的方式
{
	long long wood=0;
	    for (int t:trees) 
		{
	        if (t>H) {
	            wood+=t-H;
	        }
	    }
	    return wood;
}
int main()
{
	int n,k;
	cin>>n>>k;
	vector<int> tree(n);
	for(int i=0;i<n;i++)
	{
		cin>>tree[i];
	}
	int l=0,hi=*max_element(tree.begin(), tree.end());//取数列中最大值
	int ans=0;
	while(l<=hi)
	{
		int mid=l+(hi-l)/2;//这地方死记硬背就行了
		if (gt(tree,mid)>=k) 
			{
		        ans=mid; 
		        l=mid+1; 
		    } 
		else 
			{
		        hi=mid-1;
		    }
	}
	cout<<ans;
	return 0;
}