题意：​ 现在有一条河，河中有n个石头，你需要从河的一端到河的另一端。现在你有一次机会在任意位置放置一个石头，请问石头放在哪里可以使过河的最长路径最短。请输出放置的石头坐标。思路：​ n的规模是\(1e3\)，所以可以做到\(n^2\)的算法，我们把起点和终点也当做一块石头，基于贪心的思想，可以知道使最长路径最短的放法一定是在两个石子的中间点放。先预处理出起点到各个点的最短路和终点反跑到各个点的最短路，然后\(n^2\)枚举两个石头间距并将其缩短一半，更新答案。#includeusingnamespacestd;#definerep(i,a,n)for(inti=a;iPII;constint

题意：​ 现在有一条河，河中有n个石头，你需要从河的一端到河的另一端。现在你有一次机会在任意位置放置一个石头，请问石头放在哪里可以使过河的最长路径最短。请输出放置的石头坐标。思路：​ n的规模是\(1e3\)，所以可以做到\(n^2\)的算法，我们把起点和终点也当做一块石头，基于贪心的思想，可以知道使最长路径最短的放法一定是在两个石子的中间点放。先预处理出起点到各个点的最短路和终点反跑到各个点的最短路，然后\(n^2\)枚举两个石头间距并将其缩短一半，更新答案。#includeusingnamespacestd;#definerep(i,a,n)for(inti=a;iPII;constint