二分代码求调
  • 板块P1564 膜拜
  • 楼主Exber
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/5/9 11:39
  • 上次更新2023/11/4 23:30:04
查看原帖
二分代码求调
251130
Exber楼主2021/5/9 11:39

rt,WA 了三个点,实在找不出错误 /kk

#include <iostream>
#include <cstdio>

using namespace std;

int n,m,a[2505],sum[2][2505];

inline int mabs(int x)
{
	return x<0?-x:x;
}

bool check(int mid)
{
	int pos=1,cnt=0;
	while(pos<=n)
	{
		cnt++;
		for(int i=n;i>=pos;i--)
		{
			if(
			(mabs((sum[0][i]-sum[0][pos-1])-(sum[1][i]-sum[1][pos-1]))<=m)
			||(sum[1][i]-sum[1][pos-1]==0)
			||(sum[0][i]-sum[0][pos-1]==0)
			)
			{
				pos=i+1;
				break;
			}
		}
	}
	return cnt<=mid;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum[0][i]=sum[0][i-1]+(a[i]==1);
		sum[1][i]=sum[1][i-1]+(a[i]==2);
	}
	int l=1,r=n,ans=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	printf("%d\n",ans);
	return 0;
}
2021/5/9 11:39
加载中...