題目鏈接

題意

給你N個線段（一條直線上），問刪去一個之后，最長公共長度

AC

• 先考慮不刪邊，有兩種情況
  
• 所有直線在一起分布
  
  顯然公共部分是排序之后的（第一個右端點 - 最后一個左端點）
• 直線不在一起分布
  
  這時按照（第一個右端點 - 最后一個左端點）得到的結果是負數，最后可以加個判斷，可以解決這個情況
• 知道上面的兩種情況后，可以在O(1)的時間求出最長的公共部分，將所有的線段按照左端點升序，右端點升序，然后模擬刪邊，O(n)

// 數組模擬 #include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <algorithm> #define ll long long #define N 300005 using namespace std;int l[N], r[N]; struct seg{int l, r; }a[N]; int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < n; ++i) {scanf("%d%d", &a[i].l, &a[i].r);l[i] = a[i].l;r[i] = a[i].r;}sort(l, l + n);sort(r, r + n);int ans = 0; // 初始為0，避免負數 for (int i = 0; i < n; ++i) { int end_l = l[n - 1]; // 最后一個左端點 int begin_r = r[0]; // 第一個右端點 if (end_l == a[i].l) end_l = l[n - 2]; // 如果刪邊為最后一個左端點，左移一位 if (begin_r == a[i].r) begin_r = r[1]; // 如果刪邊為第一個右端點，右移一位 int len = begin_r - end_l;ans = max(ans, len);}printf("%d\n", ans);}return 0; } // multiset #include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <algorithm> #define ll long long #define N 300005 using namespace std;int l[N], r[N]; multiset<int> l_, r_; int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < n; ++i) {scanf("%d%d", &l[i], &r[i]);l_.insert(l[i]);r_.insert(r[i]);}int ans = 0;for (int i = 0; i < n; ++i) {// 刪除當前邊 l_.erase(l_.find(l[i]));r_.erase(r_.find(r[i]));// 找到最大值 ans = max(ans, *(r_.begin()) - *(--l_.end()));// 撤銷刪除 l_.insert(l[i]);r_.insert(r[i]);}printf("%d\n", ans);l_.clear();r_.clear();}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Codeforces Round #506 (Div. 3) - C. Maximal Intersection （思维，模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。