满分解法（100 分）

决定结束时刻的是最慢的一队

所有队伍同时开始，因而一种分队方案的结束时刻，是这套方案中最大的两人能力和。虽然所有队伍的耗时之和固定，但把两位高能力同学放在一起，可能使某一队明显更慢。因此需要平衡各队的耗时，而不是对总和做优化。

例如四人的能力为 $1,4,6,10$。三种分队方式的最长耗时分别为：

这个例子提示我们尝试让能力较大的人与能力较小的人配对。接下来需要证明，这种选择在人数更多、能力值重复时也不会错。

为什么可以先配最小值和最大值

考虑还没有分队的同学，取其中能力最小的一人和能力最大的一人，记他们的能力分别为 $a,d$。我们证明：存在一个最优方案，把这两人分在同一队。

取一个最优方案。如果 $a,d$ 已在同一队，无需调整。否则，他们分别属于两队 $(a,b)$ 和 $(c,d)$，这里 $b,c$ 是原来的搭档能力。将这两队改为

调整仍然使用原来这四个人，每人恰好一次，因此没有破坏分队的合法性。又因为 $a$ 最小、$d$ 最大，必有

所以两支新队伍的耗时，都不超过原来 $(c,d)$ 这一队的耗时；其余队伍不变，整个方案的最长耗时不会增加。原方案已经最优，调整后仍然最优。

因此可以放心固定最小与最大这对同学。去掉他们以后，对剩余同学重复同样的论证，就得到“每次配剩余最小值与最大值”的贪心方法。论证只用了非严格大小关系，所以允许不同同学具有相同能力值。

注意，这不是说答案一定等于最初的最小值加最大值。例如能力为 $1,6,6,10$ 时，先配出的 $1+10=11$ 并非最终答案；剩下两人的耗时为 $6+6=12$，必须取整个过程的最大值。

不展开人数，而是整批消耗种类

总人数可能达到 $10^{10}$，即使能力种类很少，也不能把每位同学逐个存下来，更不能每次只配一队。

将输入中的记录按能力值递增排序。设当前还未用完的能力种类位于闭区间 $[l,r]$，每个种类保存其剩余人数。由于一直使用剩余的最小、最大能力，区间两端正好是下一次要选择的种类。

当 $l<r$ 时，设两端能力为 $y_l,y_r$，剩余人数为 $c_l,c_r$。在任一端用完之前，下一对人的能力始终是这两个值。因此可以一次完成

次同样的配对。这批队伍的耗时都为 $y_l+y_r$，只需用这个值更新一次答案，然后令

若左端用完就令 $l$ 右移，若右端用完就令 $r$ 左移；两端同时用完时，两个指针都必须移动。这样下一轮的两个端点仍然具有正的剩余人数。

例如，三个能力种类分别为 $2,5,9$，对应人数为 $3,1,2$。先把 $2$ 与 $9$ 配成两队，耗时都是 $11$；能力 $9$ 的两人已经用完，而能力 $2$ 还剩一人。接着把这人与能力 $5$ 的一人配队，耗时为 $7$。答案是 $11$。这个过程只进行了两次批量操作，而不是把“一个种类”当作“一个人”处理。

只剩一种能力时如何结束

若 $l=r$，剩余同学的能力全部相同。此前每次都移除了偶数个人，而原总人数为偶数，所以这时剩余人数一定为正偶数。这些同学只能在该种类内部两两配对，每队耗时为 $2y_l$。用它更新答案后即可结束，不能遗漏这一步。

若两端同时耗尽后变成 $l>r$，则已经没有剩余同学，直接结束，不再产生任何配对。

初始答案为 $0$，每次用当前批次的耗时取最大值。贪心方法对应一个最优分队方案，而批量处理只是合并了连续相同的操作，所以最终得到的最大值就是题目要求的最短完成时间。

复杂度

时间复杂度为 $O(n\log n)$。排序需要 $O(n\log n)$，之后每次批量操作至少使一种能力耗尽，至多进行 $O(n)$ 次操作，不依赖总人数 $m$。

空间复杂度为 $O(n)$。保存 $n$ 条能力与人数记录，排序和双指针都在这些记录上操作，不创建长度为 $m$ 的数组。

AC 代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  int n;
  cin >> n;
  vector<pair<int, i64>> a(n);
  for (auto& [y, cnt] : a) cin >> cnt >> y;
  sort(a.begin(), a.end());
  int ans = 0;
  for (int l = 0, r = n - 1; l <= r; ) {
    if (l == r) {
      ans = max(ans, 2 * a[l].first);
      break;
    }
    ans = max(ans, a[l].first + a[r].first);
    i64 cnt = min(a[l].second, a[r].second);
    a[l].second -= cnt;
    a[r].second -= cnt;
    if (a[l].second == 0 && a[r].second == 0) {
      l++;
      r--;
    } else if (a[l].second == 0) {
      l++;
    } else {
      r--;
    }
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

反复扫描极值（通过子任务 1，共 30 分）

利用种类少，直接寻找下一对极值

本方法保证通过子任务 1，即 $n\le 50$。这里限制的是能力种类数，而不是总人数；总人数依然可能达到 $10^{10}$，因此仍然需要按种类保存剩余人数。

因为所有队伍同时开始，我们要最小化各队耗时的最大值。每次可以将剩余同学中能力最小和最大的一人配成一队。

这一选择可以用交换证明。设最小、最大能力为 $a,d$。取一个最优分队方案，若他们已在同一队，则直接保留；否则设涉及他们的两队为 $(a,b)$ 和 $(c,d)$，改成 $(a,d)$ 和 $(b,c)$。由于 $a\le c$、$b\le d$，两支新队伍的耗时都不超过原来的 $c+d$，所以调整后最长耗时不会增加。于是存在一个最优方案包含这对同学，去掉他们后可以重复这一选择。

每轮扫描所有种类

不必预先排序。保留输入的 $n$ 条记录，每一轮直接扫描全部种类，忽略剩余人数为零的种类，找出剩余能力的最小值和最大值。

如果不存在剩余种类，所有人已完成分队，循环结束。若只有一个种类剩余，则剩余人数为偶数，内部配对的耗时为该能力的两倍；更新答案后结束。

否则，设找到的两个种类分别有 $c_l,c_r$ 人。一次把其中较小的人数 $\min(c_l,c_r)$ 配完，记录两端能力之和，并从两个种类的剩余人数中扣去这个数量。重复扫描，直到没有剩余同学。答案始终取所有已产生耗时的最大值，而不是只保留最后一批的耗时。

每轮的批量配对与逐人执行贪心完全一致，只是把能力和相同的一批队伍合并处理，因此得到的分队方案仍然最优。

复杂度与适用范围

时间复杂度为 $O(n^2)$：每次批量配对至少耗尽一种能力，至多进行 $n$ 轮，每轮扫描 $n$ 条记录。对于 $n\le 50$ 的子任务可以直接使用。

空间复杂度为 $O(n)$，只记录各类能力和剩余人数。

算法在更大的合法输入上也保持正确，但反复扫描的时间代价过高，不能保证通过全范围。满分方法将种类预先排序，使剩余极值能直接由两个端点取得，避免每轮重新扫描。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  int n;
  cin >> n;
  vector<pair<int, i64>> a(n);
  for (auto& [y, cnt] : a) cin >> cnt >> y;
  int ans = 0;
  for (;;) {
    int l = -1, r = -1;
    for (int i = 0; i < n; i++) {
      if (a[i].second == 0) continue;
      if (l == -1 || a[i].first < a[l].first) l = i;
      if (r == -1 || a[i].first > a[r].first) r = i;
    }
    if (l == -1) break;
    ans = max(ans, a[l].first + a[r].first);
    if (l == r) break;
    i64 cnt = min(a[l].second, a[r].second);
    a[l].second -= cnt;
    a[r].second -= cnt;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}