二分70分求优化!!!悬赏关注+赞博客!!!
  • 板块P9519 pay
  • 楼主哈哈人生
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/8/13 10:29
  • 上次更新2023/11/3 04:08:53
查看原帖
二分70分求优化!!!悬赏关注+赞博客!!!
782904
哈哈人生楼主2023/8/13 10:29

球球大佬看一下代码,如何优化(题解代码太乱了,不懂qwp)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1000005],b[1000005],c[1000005],v[1000005],maxx=-1;
bool check(int x){
	for(int i=1;i<=n;i++)c[i]=a[i];
	for(int i=1;i<=m;i++){
		for(int j=max(b[i]-x+1,1ll);j<=min(b[i]+x-1,n);j++){
			c[j]-=x-abs(j-b[i]);
		}
	}
	for(int i=1;i<=n;i++)if(c[i]>0)return false;
	return true;
}
signed main(){
    std::ios::sync_with_stdio(false); 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxx=max(maxx,a[i]);
	}
	for(int i=1;i<=m;i++)cin>>b[i];
	int l=0,r=maxx+n-1;
	while(l<r){
	    int mid=l+r>>1;
		if(check(mid)==1)r=mid;
		else l=mid+1;
	}
	cout<<l;
	return 0;
} 
2023/8/13 10:29
加载中...