#212064. [KTSC 2021] 射击游戏 / gun

本题翻译自 2021년도 국제정보올림피아드 대표학생 선발고사 2차 선발고사 #1 총 쏘기。

请注意，你不需要也不应该实现 main 函数。具体实现方式见【实现细节】部分。

警告：滥用本题评测一次即可封号。

有一款由两名玩家共同参与的在线射击游戏。游戏的目标是在一个虚构的城市中摧毁建筑物。

游戏中， 座建筑物从左到右排列在水平地面上。建筑物从左到右依次编号为 到 。每座建筑物的高度用一个序列 （）表示，且 是 到 之间互不相同的整数。

两名玩家从所有建筑物左侧的同一位置出发。在时间 （）时，两名玩家同时发射一发子弹，子弹从发射位置水平向右飞行。两发子弹的速度相同。玩家可以选择子弹的发射高度 ，即从地面到子弹的垂直距离， 为 到 之间的整数。两名玩家可以选择相同的发射高度。

如果玩家选择的发射高度为 ，则子弹会摧毁满足 且未被摧毁的最左侧建筑物。如果没有满足条件的建筑物，则不会发生任何事。如果两名玩家的子弹同时满足条件且目标建筑物相同（由于子弹速度相同），则只有该建筑物会被摧毁。特别地，如果两名玩家的发射高度相同，则始终只有一个建筑物被摧毁。例如，若 ，，且两名玩家均选择 ，则只有建筑物 会被摧毁。

问题的目标是：给定 座建筑物的高度，找到摧毁所有建筑物的最短时间 ，以及每个时间点两名玩家的子弹发射高度。

实现细节

你需要实现以下函数：

vector< pair<int, int> > min_shooting_buildings(vector<int> A)

• 该函数仅被调用一次。
• 参数 是一个长度为 的数组， 表示建筑物 的高度 （）。
• 该函数返回一个长度为 的数组 ，其中 是摧毁所有建筑物的最短时间。数组 的每个元素 表示两名玩家的子弹发射高度。

在提交的源代码中，任何地方都不允许调用输入输出函数。

示例评分程序的输入格式如下：

• 第 行：
• 第 行：

示例评分程序的输出格式如下：

• 第 行（）：函数 min_shooting_buildings 返回的数组的第 个元素。

注意：示例评分程序可能与实际评分程序不同。

样例输入 1

4
1 2 4 3

样例输出 1

2
1 4
2 3

样例输入 2

8
4 3 8 2 1 7 6 5

样例输出 2

4
4 8
3 7
2 6
1 5

样例输入 3

8
5 6 7 1 2 8 3 4

样例输出 3

4
5 6
7 8
1 2
3 4

约束条件

• （）
• （）互不相同。

子任务

1. （ 分）
   • 不存在 满足 。
2. （ 分）
   • 不存在 满足 。
3. （ 分）
   • 。
4. （ 分）
   • 。
5. （ 分）
   • 。
6. （ 分）
   • 。
7. （ 分）
   • 无额外约束。

评分标准

如果函数 min_shooting_buildings 返回的数组长度 为摧毁所有建筑物的最短时间，且按返回的数组发射子弹能摧毁所有建筑物，则该测试用例视为正确。

示例

• 示例 1：，。

  调用函数：

  min_shooting_buildings([1, 2, 4, 3])`
  

  如图 1 所示，若两名玩家按 发射子弹，可在时间摧毁所有建筑物。

  

  如图 2 所示，若按 发射子弹，可在时间 摧毁所有建筑物。

  

  因此，函数应返回长度为 的数组，例如 [(1, 4), (2, 3)]。

• 示例 2：，。

  函数应返回长度为 的数组，例如 [(4, 8), (3, 7), (2, 6), (1, 5)]。

• 示例 3：，。

  函数应返回长度为 的数组，例如 [(5, 6), (7, 8), (1, 2), (3, 4)]。