分块做法,只过了hack点,玄关
查看原帖
分块做法,只过了hack点,玄关
737219
YONEX楼主2025/2/5 16:46

RT

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
// const long long char_z=0;
//ios::sync_with_stdio(0);cin.tie(),cout.tie();
int k[100005];int m,n,p;int a,b,c;ll ans=0;
int pos[100007]/*判断点属于哪一个块*/;
int maxn=0,max_num[100000];
int minn=0,min_num[100000];
int line_l[100007],line_r[100007];
int t;int kp=0;
inline long long read()
{
	char cc=getchar();long long f=1,ans=0;
	while(cc<'0' or cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0' and cc<='9'){ans=(ans*10)+(cc-'0');cc=getchar();}return f*ans;
}
inline void reads(){n=read();m=read();for(int i=1;i<=n;i++)k[i]=read();}
inline void build()
{
	t=sqrt(n);//块的个数 
	for(int i=1;i<=t;i++){line_l[i]=(i-1)*t+1;line_r[i]=i*t;}//设置左右边界 
	if(line_r[t]<n){t++;line_l[t]=line_r[t-1]+1;line_r[t]=n;}//特判最后一个块不完整 
	for(int i=1;i<=t;i++) 
	for(int j=line_l[i];j<=line_r[i];j++){pos[j]=i;} 
	for(int i=1;i<=t;i++){maxn=0;for(int j=line_l[i];j<=line_r[i];j++){maxn=max(k[j],maxn);}max_num[i]=maxn;}
	for(int i=1;i<=t;i++){minn=10000000;for(int j=line_l[i];j<=line_r[i];j++){minn=min(k[j],minn);}min_num[i]=minn;}
}
inline void askk() 
{ 
	for(int i=1;i<=m;i++) 
	{ 
	a=read();kp=10000000;
	for(int j=1;j<=t;j++)kp=min(min(abs(max_num[j]-a),abs(min_num[j]-a)),kp);
	ans+=kp;
	}
	cout<<ans;
} 
inline void main_d(){reads();build();askk();} 
int main(){main_d();return 0;}
2025/2/5 16:46
加载中...