计蒜客 -光合作用-二分查找

蒜头是个爱学习的孩子，他总喜欢在生活中做一些小实验，这次蒜头想研究一下光合作用。

蒜头的实验材料有如下几样：神奇的种子，普通的纸箱和一些光源。一开始，蒜头将种子均匀的种在了箱子底部，你可以将其看成 $X$轴，种子的位置为 $X$ 轴上的点。然后蒜头用纸板将箱子盖住，并在纸板上安装了一些光源（具体见图）。神奇的种子会在有光的情况下一直向上生长直到没光为止。现在蒜头想知道当实验结束时每颗种子的高度是多少？

顶上的为光源，光源两边与顶部的夹角都为 45^{\circ}45​∘​​，黄色部分为光照，绿色的为植物。

第一行输入一个整数 $T$，表示测试数据的组数。

每组数据的第一行是三个整数 n,m,H(1 \leq n,m \leq 10^5, 0 \leq m \leq 10^5, 1 \leq H \leq 10^4)n,m,H(1≤n,m≤10​5​​,0≤m≤10​5​​,1≤H≤10​4​​)，$n$ 表示种子数(编号为 $1\cdots n$)，$m$ 表示光源数，$H$ 表示箱子的高度。

接下来 $m$ 行，每行一个整数 X_iX​i​​ 表示第 $i$ 个光源在顶部的位置。

所以更换一种思路，对每个点查找它相邻的两个光源比较哪个更近，算法复杂度为nlogm，优化了。

#include <bits/stdc++.h>
using namespace std;
#define maxv 100000+5
int N,M,H;//种子，光源，高度
int b[maxv],a[maxv];
void func(int i)//求解第i个种子的高度
{int pos=lower_bound(a+1,a+M+1,i)-a;//找到离第i个最近的光源，进行比较//cout<<i<<" "<<pos<<endl;//  cout<<H-(a[pos]-i)<<" H"<<H<<" POS"<<a[pos]<<endl;if(pos==1)b[i]=max(b[i],H-(a[pos]-i));else if(pos==M+1)b[i]=max(b[i],H-(i-a[pos-1]));elseb[i]=max(b[i],max(H-(i-a[pos-1]),H-(a[pos]-i)));}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d%d",&N,&M,&H);memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=1;i<=M;i++)scanf("%d",&a[i]);sort(a+1,a+M+1);for(int i=1;i<=N;i++){if(M!=0)func(i);printf("%d\n",b[i]);}}return 0;
}