火烧赤壁
隔了一天再来理解就想对来说舒服多了,也不知道是不是因为昨天太忙了没有专心....
参考:
思路:首先必须要明白一点,这道题需要将船只的位置标记出来,但是看到数据为
(-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;
}