Meetings S 题解

题目描述

有两个牛棚位于一维数轴上的点 \(0\) 和 \(L\) 处。同时有 \(N\) 头奶牛位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 \(i\) 初始时位于某个位置 \(x_i\)，并朝着正向或负向以一个单位每秒的速度移动，用一个等于 \(1\) 或 \(-1\) 的整数 \(d_i\) 表示。每头奶牛还拥有一个在范围 \([1,10^3]\) 内的重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：

如果奶牛 \(i\) 移动到了一个牛棚，则奶牛 \(i\) 停止移动。
当奶牛 \(i\) 和 \(j\) 占据了相同的点的时候，并且这一点不是一个牛棚，则发生了相遇。此时，奶牛 \(i\) 被赋予奶牛 \(j\) 先前的运动方向，反之亦然。注意奶牛可能在一个非整数点相遇。
令 \(T\) 等于停止移动的奶牛（由于到达两个牛棚之一）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 \(0 \ldots T\)（包括时刻 \(T\)）之间发生的奶牛对相遇的总数。

输入格式

输入的第一行包含两个空格分隔的整数 \(N\) 和 \(L\)。

以下 \(N\) 行，每行包含三个空格分隔的整数 \(w_i\) ，\(x_i\) 以及 \(d_i\) 。所有的位置 \(x_i\) 各不相同，并且满足 \(0<x_i<L\)。

输出格式

输出一行，答案，即在时刻 \(0 \ldots T\)（包括时刻 \(T\)）之间发生的奶牛对相遇的总数。

样例输入

样例输出

分析

首先，这道题是个二分没跑了

我们二分查找符合的停下时间 \(mid\)，然后在算出在这期间有多少牛相遇即可

Part 1 如何写二分中的check函数？

我们先来看几个结论：

（1）： 假设两只牛发生相遇事件，\(1\) 为牛的速度，\(W\) 为牛的体重，故一次相遇事件可以表述成下图。

A(1, WA)-------> <--------B(1, WB)

<-------A(1, WA) B(1, WB)-------->

如果我们先不看牛的速度，只看体重，那么：

WA-------> <--------WB

<-------WA WB-------->

所以我们可以看作两只牛相遇后，方向保持不变，但交换了身体。艺术带师？

（2）： 还是（1）的这幅图。

你会发现当两只牛相遇之后，这两只牛的相对位置是没有改变的。也就是说在任何时候整个数轴上从左往右的第 \(i\) 只牛的信息一定是最初输入的 \(C[i]\)。

WA-------> <--------WB

<-------WA WB-------->

（3）： 由（1）我们可以把每次的相遇看作不改变牛的方向，但改变了重量。

可以推出当一只牛在 \(a\) 处时，\(T\) 秒后一定会有一只牛在同一方向的 \(a + T\) 处。

又因为（2）而如果我们知道了这头牛是当时整个数轴上的从左往右第几头，那么就一定可以知道这头牛的相关信息

所以很容易写出 \(check\) 函数:

bool check(int t) {

	int W = 0; // 到达牛棚的牛的总重量

	int s = 1, e = n;

	// 根据（2）：牛的相对位置不变

	// 直接表示出某一头相对位置确定的牛

	for(int i = 1; i <= n; i++) { // 根据（3）

		if(cow[i].d == 1)

			if(cow[i].x + t >= L) { // 如果t分钟后有牛到了右牛棚

				W += cow[e].w;

				// 此牛一定是目前所在位置最靠右且未到达右牛棚的牛

				// 累加总重量

				e--;

				// 更新目前位置最靠右的牛的位置

			}

		else {

			if(cow[i].x - t <= 0) { // 同

				W += cow[s].w;

				s++;

			}

		}

	}

	return s >= sum;

}

Part 2 如何在知道时间的情况下计算出答案？

很简单嘛，题目要求我们算出在这个时间段内发生了多少次牛的相遇事件。

那么我们就单独看每只向左走的牛，如果能算出与它们每只牛在这个时间段中与多少只向右走的牛相遇，答案也就迎刃而解了（毕竟所有向左走的牛发生的相遇事件的总数就是我们的答案

那么，如何求出可以和它相遇的往右走的最左边的牛呢？

同样使用二分：

int work(int t) { // 答案函数

	int len = 0, ans = 0;

	for(int i = 1; i <= n; i++) {

		if(cow[i].d == -1) { // 枚举每只向左走的牛

			int x_ = cow[i].x - t * 2;

			int l = 0, r = len + 1;

			while(l + 1 < r) {  // 找出能与这头向左走的牛相遇的最左边的牛

				int mid = (l + r) >> 1;

				if(f[mid] >= x_) r = mid;

				else l = mid;

			}

			ans += (len - r + 1);

			// r是最左边的牛能与i相遇的牛，而len是目前所有向右走的牛的个数

			// 所以len-r+1就是在这一个时间段i牛能与几头向左走的牛相遇

		}

		else f[++len] = cow[i].x; // 记录每只向右走的牛

	}

	return ans;

}

我要调疯了。。。

AC代码

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 50005;

struct data { // 牛的信息

	int w, x, d;

	int id;

	// w表示牛的重量，x表示牛的初始位置，d表示牛的行动方向

	// id表示牛的初始编号（从左到右

} cow[MAXN], ans[MAXN];

bool cmp(data a, data b) {

	return a.x < b.x; // 按初始位置排序

}

int n, L; // 有n头牛，数轴上最右边的牛棚的距离为L

int sum = 0; // 牛的总重量

int f[MAXN];

bool check(int t) {

	int W = 0; // 到达牛棚的牛的总重量

	int s = 1, e = n;

	// 根据（2）：牛的相对位置不变

	// 直接表示出某一头相对位置确定的牛

	for(int i = 1; i <= n; i++) { // 根据（3）

		if(cow[i].d == 1) {

			if(cow[i].x + t >= L) { // 如果t分钟后有牛到了右牛棚

				W += cow[e].w;

				// 此牛一定是目前所在位置最靠右且未到达右牛棚的牛

				// 累加总重量

				e--;

				// 更新目前位置最靠右的牛的位置

			}

		}

		else {

			if(cow[i].x - t <= 0) { // 同

				W += cow[s].w;

				s++;

			}

		}

	}

	return W * 2 >= sum;

}

int work(int t) { // 答案函数

	int len = 0, ans = 0;

	for(int i = 1; i <= n; i++) {

		if(cow[i].d == -1) { // 枚举每只向左走的牛

			int x_ = cow[i].x - t * 2;

			int l = 0, r = len + 1;

			while(l + 1 < r) {  // 找出能与这头向左走的牛相遇的最左边的牛

				int mid = (l + r) >> 1;

				if(f[mid] >= x_) r = mid;

				else l = mid;

			}

			ans += (len - r + 1);

			// r是最左边的牛能与i相遇的牛，而len是目前所有向右走的牛的个数

			// 所以len-r+1就是在这一个时间段i牛能与几头向左走的牛相遇

		}

		else f[++len] = cow[i].x; // 记录每只向右走的牛

	}

	return ans;

} 

int main() {

	scanf ("%d %d", &n, &L);

	for(int i = 1; i <= n; i++) {

		scanf ("%d %d %d", &cow[i].w, &cow[i].x, &cow[i].d);

		sum += cow[i].w;

		cow[i].id = i;

	}

	sort(cow + 1, cow + n + 1, cmp);

	int l = 0, r = 1e9, t = 0;

	// l最小为1

	// r最小为L，即开始在数轴上0的牛都已经走到了最右边的牛棚

	while(l <= r) { // 二分时间

		int mid = (l + r) >> 1;

		if(check(mid)) {

			r = mid - 1;

			t = mid;

		}

		else l = mid + 1;

	}

	printf("%d", work(t));

	// 算出有多少头牛在此时间内相遇过

	return 0;

}

巴特西