Zerojudge k572 題解

離散化這個字光是聽起來就超帥

題目

第一行輸入 N 筆資料
每筆資料有一個區間 [L,R]
求出重疊最多的數字，若相同則輸出最大者
Zerojudge題目連結

測資

Example 1:

Input:
3
19 25
23 26
18 20
Output:
25

Example 2:

Input:
2
-1000000000 999999995
-999999995 1000000000
Output:
999999995

解題關鍵

整個程式最重要的邏輯就是:
最優解一定會出現在剛剛輸入的一堆範圍中 某個範圍的邊界值
因為對於兩個重疊的範圍，

如:

-XXXXX---
---OOOOO-
123456789

若有一個重疊且非邊界，如:5
則必存在一個重疊且邊界，如:6，則6為最佳解

這時候就可以利用 map 非連續的特性
只對邊界進行處裡，而非整個範圍

程式碼

/*
這個程式用差分數列去計算 map
個人覺得超級巧妙
因為 map 本身會用 key 值排序
這樣在做前綴和時
就自然會包含剛剛輸入的所有座標
*/
#pragma GCC optimize("Ofast,fast-math,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#define SIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl "\n"

int main(){
    SIO;
    int n;
    map<int,int> mp;
    cin >> n;
    for(int i = 0; i<n; i++){
        int l, r;
        cin >> l >> r;
        mp[l]++;
        if(!mp[r]) mp[r]; // 注意這行
        /*
        因為如果只是照一般差分數列，不寫這行的話
        就會處理不到 r 的位置
        所以 mp[r] 必須有一個值
        設定為 0 的話也不會影響到差分數列
        */
        mp[r+1]--;
    }
    /*
    這邊不先計算前綴和
    而是直接用 tmp 這個變數去加，可以簡化程式
    所以 tmp 就會是與運行到 mp[i] 的前綴和相等
    */
    int tmp = 0; // 相當於算完前綴和後的 mp[i].second
    int ans = 0; // 最優解的值
    int ind = -1; // 最優解的座標
    for(auto &i:mp){
        tmp += i.second;
        if(tmp > ans){
            ans = tmp;
            ind = i.first;
        }
        else if(tmp == ans){
            ind = max(ind, i.first); // 座標優先取大者
        }
    }
    cout << ind;
    return 0;
}