Meeting on the Line codeforces 1730B

Problem - B - Codeforces

题目大意：有n个人分布在数轴上，给出每个人的坐标位置xi,和出发前得到准备时间ti，要求选定一个位置x0，使得每个人到达这个地方的时间的最大值最小

1<=n<=2e5;1<=xi<=1e8;1<=ti<=1e8

思路：首先我们可以考虑如果ti全部等于0的时候，那么到达时间最大值的最小值肯定是数轴上最靠左的点和最靠右的点的中点，那么再看有ti的时候，当准备时间最长的那个人准备好了之后，也可以按照ti全等于0的思路考虑，需要找到这时数轴上最靠左和最靠右的点，我们要让时间最小，很显然要让靠左的点尽可能向右走，靠右的点尽量向左走，那么我们可以遍历所有点，对于每个人，算出在他准备好到准备时间最长的人准备好的这段时间里，向右走到的最远位置，在所有人中取最小值 ，和向左走到的最远位置，在所有人中取最大值，这两个数值分别为最靠左和最靠右的点，取中点即可

#include
#include
using namespace std;
const int N = 1e5 + 5;
int x[N], ti[N], pos[N];
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &x[i]);
		}
		int ma = 0,cnt=0;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &ti[i]);
			ma = max(ma, ti[i]);//找出准备时间最长的人			
		}
		int mix = 0x7fffffff, maxx = 0;	
		for (int i = 1; i <= n; i++)
		{
			mix = min(mix, x[i] + ma - ti[i]);//找出向右到达的位置的最小值
			maxx = max(maxx, x[i] - (ma - ti[i]));//找出向左到达的位置的最大值
		}
		printf("%.6lf\n", (maxx + mix) * 1.0 / 2);//最靠左和最靠右的两个点取中点
	}
	return 0;
}