火烧赤壁

火烧赤壁

隔了一天再来理解就想对来说舒服多了，也不知道是不是因为昨天太忙了没有专心....

参考：

火烧赤壁 题解

火烧赤壁题解

思路：首先必须要明白一点，这道题需要将船只的位置标记出来，但是看到数据为(-1e9,1e9)就可以知道，很明显直接用一个数组来储存是不可能的。但是因为数据的个数不多，所以我们就可以考虑使用离散化来标记数据。

代码：

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], b[maxn],x[maxn<<1];
int add[maxn << 1];
int main()
{
    ios::sync_with_stdio(false);
    int n,cnt=0;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i], x[++cnt] = a[i], x[++cnt] = b[i];
    sort(x + 1, x + cnt + 1);
    cnt = unique(x + 1, x + cnt + 1) - x - 1;
    for (int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(x + 1, x + cnt + 1, a[i]) - x;
        b[i] = lower_bound(x + 1, x + cnt + 1, b[i]) - x;
        add[a[i]]++;
        add[b[i]]--;
    }
    ll ans = 0;
    ll temp = 0;
    for (int i = 1; i <= cnt; ++i)
    {
         temp+= add[i];
        if (temp > 0) ans += x[i + 1] - x[i];
    }
    cout << ans << endl;
}