[JOI 2020 Final] 長いだけのネクタイ
Description
Input
Output
Sample Input
样例 1 输入:
3
4 3 7 6
2 6 4
样例 2 输入:
5
4 7 9 10 11 12
3 5 7 9 11
Sample Output
样例 1 输出:
2 2 1 1
样例 2 输出:
4 4 3 2 2 2
Data Constraint
题解
好不容易模拟赛有一道签到题
首先可以显然证明,在拿掉一个领带后,将剩下的领带长度从大到小排序,把人本来戴着的领带长度从小到大排序,然后一一对应来取(max(0,a[i]-b[i]))是可以使最大值最小的
然后我们就可以每次都这样做,于是可以得到一个(O(n^2 log n))的算法,只能拿到50分
显然以上算法浪费了很多的操作,我们知道将(n+1)个领带排好序后,取一个领带出来,那这个领带左边的(也就是比它长的)贡献是不会受到影响的
所以我们可以写两个线段树,一个统计排序后的(max(0,a[i]-b[i]))的区间最大值(max1),一个统计排序后的(max(0,a[i+1]-b[i]))的区间最大值(max2)
然后找到拿走的领带在排序后的位置(num),查询这个点左边的(max1)和右边的(max2)再取较大的那个即可,复杂度(O(n log n))轻松通过
当然也可以记录前缀最大值和后缀最大值然后进行相同的操作,复杂度(O(n))
CODE(线段树法)
#include<cstdio>
#include<string>
#include<algorithm>
#define R register int
#define N 200005
#define ll long long
using namespace std;
int n,tree1[N<<2],tree2[N<<2],num[N],c1[N],c2[N],b[N];
struct arr{int x,id;}a[N];
int max(int a,int b) {return a>b?a:b;}
int min(int a,int b) {return a<b?a:b;}
void read(int &x)
{
x=0;int f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
bool cmp(arr x,arr y) {return x.x>y.x;}
bool cmp1(int x,int y) {return x>y;}
void build1(int u,int l,int r)
{
if (l==r) {tree1[u]=c1[l];return;}
int mid=l+r>>1;build1(u<<1,l,mid);build1(u<<1|1,mid+1,r);
tree1[u]=max(tree1[u<<1],tree1[u<<1|1]);
}
void build2(int u,int l,int r)
{
if (l==r) {tree2[u]=c2[l];return;}
int mid=l+r>>1;build2(u<<1,l,mid);build2(u<<1|1,mid+1,r);
tree2[u]=max(tree2[u<<1],tree2[u<<1|1]);
}
int find1(int u,int l,int r,int x,int y)
{
if (l>=x && r<=y) return tree1[u];
int mid=l+r>>1,res=0;
if (x<=mid) res=max(res,find1(u<<1,l,mid,x,y));if (y>mid) res=max(res,find1(u<<1|1,mid+1,r,x,y));
return res;
}
int find2(int u,int l,int r,int x,int y)
{
if (l>=x && r<=y) return tree2[u];
int mid=l+r>>1,res=0;
if (x<=mid) res=max(res,find2(u<<1,l,mid,x,y));if (y>mid) res=max(res,find2(u<<1|1,mid+1,r,x,y));
return res;
}
int main()
{
read(n);
for (R i=1;i<=n+1;++i)
read(a[i].x),a[i].id=i;
for (R i=1;i<=n;++i)
read(b[i]);
sort(a+1,a+1+n+1,cmp);sort(b+1,b+1+n,cmp1);
for (R i=1;i<=n+1;++i)
num[a[i].id]=i;
for (R i=1;i<=n;++i)
c1[i]=max(a[i].x-b[i],0),c2[i]=max(a[i+1].x-b[i],0);
build1(1,1,n);build2(1,1,n);
for (R i=1;i<=n+1;++i)
{
if (num[i]==1) printf("%d ",find2(1,1,n,1,n));
else if (num[i]==n+1) printf("%d ",find1(1,1,n,1,n));
else printf("%d ",max(find1(1,1,n,1,num[i]-1),find2(1,1,n,num[i],n)));
}
printf("
");
return 0;
}