Codeforces思维训练

1721C C. Min-Max Array Transformation

给你一个非减序列 \(a1,a2.a3...a_n\)

和一个非减序列 \(b1,b2,b3...b_n\)

其中 \(b_i=a_i+d_i\)，对于每个 \(d_i\) ，求出它的最大值 \(d_1\) 和最小值 \(d_2\)

思路：最小值对应的 \(b_i\) 显然等于 \(lower\)_\(bound\)\((b+1,b+1+n,a_i)\)

因为每一个 \(a_i\) 都可以加一个最小的值变成对应的 \(b_i\) ，从而实现一一对应

最大值对应的 \(b_i\) 是难点所在：

考虑从后往前遍历算 \(d_2\)，因为最后一个（即 \(d_2[n]\) ）已经确定，它等于 \(n\);

考虑递推：当前已知 \(d_2[i+1]\)，要求 \(d_2[i]\)。

当 \(d_1[i+1]>=i+1\)（事实上这里不可能大于） 时，说明 \(i+1\) 后面的元素 \(a_i\) 只能一一分配 \(b_i\) 了。所以此时 \(a_i\) 就不能进来凑热闹了，因为进来会导致后面元素不够分配，

所以 \(d_2[i]=d1[i+1]-1\) 。

当 \(d_1[i+1]<i+1\) 时，\(a_i\) 就可以随便进来凑热闹，所以就是把 \(d_2[i]\) 设置为 \(d_2[i+1]\)。

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int b[200010];
int d1[200010];
int d2[200010];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>b[i];
		for(int i=1;i<=n;i++)
		{
			d1[i]=lower_bound(b+1,b+1+n,a[i])-b;
		}
		d2[n]=n;
		for(int i=n-1;i>=1;i--)
		{
			if(d1[i+1]>=i+1) d2[i]=d1[i+1]-1;
			else d2[i]=d2[i+1];
		}
		for(int i=1;i<=n;i++) 
		{
			cout<<b[d1[i]]-a[i]<<' ';
		}
		cout<<endl;
		for(int i=1;i<=n;i++)
		{
			cout<<b[d2[i]]-a[i]<<' ';
		}
		cout<<endl;
	}
}