2024/12/28课堂记录

#include<iostream>
using namespace std;
int a[200010],f[200010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		a[i]=a[i-1]+x;
	}
	//for(int i=1;i<=n;i++)cout<<a[i];
	int ans=-0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		f[i]=-0x3f3f3f3f;
		for(int j=i-1;j>=max(i-m,1);j--)f[i]=max(f[i],a[i]-a[j]);
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}

 #include<iostream>
using namespace std;
int a[100010];
int n,k,r=-1,l=1,ans=0;
bool half(int mid)
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		int x=a[i];
		while(x>=mid)
		{
			x-=mid;
			sum++;
		}
	}
	if(sum>=k)return 1;
	else return 0;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)r=max(r,a[i]);
	while(l<=r)
	{
//		cout<<"hhh";
		int mid=(l+r)/2;
		if(half(mid)==1)l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans;
	return 0;
}

 #include<iostream>
using namespace std;
long long int l,n,m,ans=0;
long long int a[50010];
bool half(long long int mid)
{
	long long int sum=0,now=0;//sum：可以去掉的石头总个数，now：现在跳到第几块石头上（下标 
	for(long long int i=1;i<=n+1;i++)
	{
		if(a[i]-a[now]<mid)sum++;//现在站的石头与面前的石头（可能已经移掉几块了）的距离 比预计距离小 
		else now=i;//距离比预计距离大 
	}
	if(sum<=m)return 1;
	else return 0;
}
int main()
{
	cin>>l>>n>>m;
	for(long long int i=1;i<=n;i++)cin>>a[i];
	long long int r=l;l=0;
	a[n+1]=r;
	while(l<=r)
	{
		long long int mid=(l+r)/2;
		if(half(mid)==1)ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<ans;
	return 0;
}