Luogu P1007 独木桥

题目描述

link

思路

找到独木桥的中间位置, 最少时间考虑在端点左侧的, 向左走, 在端点右侧的向右走.

最多时间考虑在端点左侧的向右走, 在端点右侧的向左走.

最少时间即为最优情况下最多的时间, 最多时间即为最差情况下的最多时间

Code

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5e3 + 10;
 
int l, n, s[N], ans = 0, ans2 = 0;

int main() {
	scanf("%d%d", &l, &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &s[i]);
	int mid = l >> 1;
	sort(s+1, s+1+n);
	for (int i = 1; i <= n; i++) {
		if (s[i] <= mid) ans = max(ans, s[i]), ans2 = max(ans2, l-s[i]+1);
		else if (s[i] > mid) ans = max(ans, l-s[i]+1), ans2 = max(ans2, s[i]);
	}
	printf("%d %d", ans, ans2);
	return 0; 
}