B. Meeting on the Line（模拟/二分/思维）

题目

题意

给定n个朋友的位置xi，以及他们出门前需要花费的化妆打扮时间ti（都是精致boy和精致girl），求一个见面地点，使得这n个朋友的见面时间最短。

思路

如果ti都是0，那么该问题退化成经典的一道碰面问题，其最佳见面地点则为最小和最大地点的平均值x = (xmin+xmax)/2。

现在多了化妆时间，那么最佳地点则会受到ti的影响。

对于所有点按xi升序排序 枚举每段可能的区间，求当前区间位置[x[i],x[i+1]]下，最佳的碰面地点。

• 那么我们可以求出前i个点，到达x[i]的最小时间。
• 求出后n-i个点，到达x[i+1]的最小时间。
• 再根据两者的到达时间，模拟求出最佳的碰面地点。

详见代码

代码

#include 
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 200010;

int n;
struct node {
	int x, t;
}a[maxn];
bool cmp(const node &a, const node &b) {
	return a.x = 0; --i) {
			printf("%d ", arr[i]);
		}
	} else {
		for (int i = 0; i  t2) {
		swap(t1, t2);
	}
	dx -= min(t2 - t1, dx); // move forward (tmax- tmin)
	return t2 + dx / 2; // need time: tmax + left distance / 2;
}

// calculate the best meeting position for two positions 
// with consumed time t1(at position dis), t2 and distance dx
double cal_dis(double t1, double t2, double dx, double dis) {
	if (t1  1) {
        int m = (l + r) / 2;
 
        int mxl = 0, mnr = INF;
        for(int i = 0; i  m) {
                mxl = INF;
                mnr = 0;
                break;
            } else {
                mxl = max(mxl, x[i] - (m - t[i]));
                mnr = min(mnr, x[i] + (m - t[i]));
            }
        }
 
        if(mxl