離散化這個字光是聽起來就超帥
題目
第一行輸入 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;
}