題目鏈接：https://codeforces.com/gym/105930/problem/G

題目背景：

????????n?名工人加工 m?個工件，第 i 個工件在第 ti 分鐘的開頭加入 工人 wi 的收件箱。 每分鐘，工人從收件箱里拿出一個工件，完成加工后放入下 一個工人的收件箱（如果是最后一個工人則加工完成）。問 所有工件加工完成需要幾分鐘。

思路：

? ? ? ? 由于每個工人每分鐘只能處理一個任務，可以先預處理出來每個任務的結束時間v[i]，既 t + n - w；再對結束時間進行升序排序，只需對其進行 ans = max(ans + 1, v[i])運算即可。可證明貪心策略成立。

數據范圍：

? ? ? ? n 總和不超過 2e5。

時間復雜度：

? ? ? ? O(nlogn)

ac代碼：?

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}/* 有乘就強轉，前綴和開ll */void solve()
{int n, m;cin >> m >> n;vi v(m + 10, 0);for (int i = 0; i < m; ++i){int a, b;cin >> a >> b;v[i] = b + n - a;}sort(v.begin(), v.begin() + m);int ans = v[0];for (int i = 1; i < m; ++i)ans = max(ans + 1, v[i]);cout << ans << endl;
}int main()
{ioscc;int T;cin >> T;while (T--)solve();return 0;
}