求助,二分写法 0 分,但是过了大多数点,神秘 WA
查看原帖
求助,二分写法 0 分,但是过了大多数点,神秘 WA
367991
Arctic_1010楼主2022/10/17 16:18

已经 #define int long long 了。

思路大概是把每次刮的风存下来,计算从开始到当前时间每个雪球相对于初始位置的偏移量。

然后二分断点找出最后一个满足相邻雪球不重叠的时间,如果下次刮向右的风,那么应该是由于下次刮风导致的整个相邻两个球的区间被完全覆盖;向左同理。

但是 WA 在了十四万行,不是很能理解。

但是我认为题解的写法和我的等价啊/kk

#include<bits/stdc++.h>
#define int long long
#define INF INT32_MAX
#define INFll INT64_MAX
using namespace std;
const int N=1e6+10;
int n,m;
int L[N],R[N],a[N];
int ans[N];
void work(int x,int len)
{
	if(L[m]+R[m]<=len)
	{
		ans[x]+=R[m];
		ans[x+1]+=L[m];
		return;
	}
	int l=1,r=m,q=-1;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(L[mid]+R[mid]<=len) l=mid;
		else r=mid-1;
	}
	q=l;
	if(L[q]==L[q+1])
		ans[x]+=len-L[q],ans[x+1]+=L[q];
	else ans[x]+=R[q],ans[x+1]+=len-R[q];
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	int tmp=0;
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;tmp+=x;
		L[i]=max(L[i-1],-tmp);
		R[i]=max(R[i-1],tmp);
	}
	
	ans[1]+=L[m],ans[n]+=R[m];
	
	for(int i=1;i<n;i++) work(i,a[i+1]-a[i]);
	
	for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
	return 0;
}

感激不尽。

2022/10/17 16:18
加载中...