题目链接
P1047 校门外的树
今天用这道题目来练习一下离散化。
当然这道题并不需要离散化,但是当数据范围开到数组开不下时离散化还是很有必要的。
题目代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include <iostream> #include <algorithm> using namespace std;
struct Node { int pos; int num; } a[100005];
int cmp(Node a, Node b) { return a.pos < b.pos; }
int l, m;
int main() { cin >> l >> m; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y;
a[i*2-1].pos = x; a[i*2-1].num = 1; a[i*2].pos = y + 1; a[i*2].num = -1; }
sort(a + 1, a + m * 2 + 1, cmp);
int sum = 0, total = 0; for (int i = 1; i <= m * 2; i++) { sum += a[i].num;
if (sum == 1 && a[i].num == 1) { total += a[i].pos - a[i-1].pos; } }
total += l - a[m*2].pos + 1;
cout << total << endl; return 0; }
|