萌新妹子刚学OI对某个公式有点不解
查看原帖
萌新妹子刚学OI对某个公式有点不解
556545
_anll_楼主2024/1/1 18:43

rt,找天数是对的(但我把初始天数从1开始算的),后面找牛的公式有点不理解为什么不能用注释的公式去找

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int n,ans,day=2147483647,area[300005],alen;
bool ok=false;
string s;
signed main(){
	cin>>n>>s;
	s='6'+s;
	for(int i=1;i<=n;i++){
		if(s[i]=='1'){
			if(!ok) ok=true,alen+=1;
			area[alen]+=1;
		}
		else{
			if(ok){
				ok=false;
				if(alen==1&&s[1]=='1') day=min(day,area[alen]);
				else day=min(day,(area[alen]+1)/2);
			}
		}
	}
	if(s[n]=='1') day=min(day,area[alen]);
	for(int i=1;i<=alen;i++){
//		if(area[i]-2*(day-1)>=0) ans+=area[i]-2*(day-1);
//		else ans+=area[i]-day+1;
		ans+=ceil(1.0*area[i]/(2*day-1));
	}
	cout<<ans;
	return 0;
}

第一行:从中间扩散的情况

第二行:从旁边扩散的情况(指左边界和右边界)

2024/1/1 18:43
加载中...