描述
曹操平定北方以后，公元208年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。
孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。
隆冬的十一月，天气突然回暖，刮起了东南风。
没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。
曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！
格式
输入格式
第一行：N
以后N行，每行两个数：Ai Bi(表示连环线上着火船只的起始位置和终点,-10^9<=Ai,Bi<=10^9)
输出格式
输出着火船只的总长度
样例1
样例输入1[复制]
3-1 15 112 9
样例输出1[复制]
11
提示
n<=20000
如果Ai=Bi是一个点则看作没有长度
题目类型：区间扫描
算法分析：将每个区间按照起始位置递增排序，判断当前区间pp的后一个区间aa[i]的开始位置是否小于pp的结束位置，如果小于，则再判断aa的结束位置是否大于pp结束位置，如果大于，则更新pp的结束位置; 否则累加当前区间的长度
|
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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 1e9 + 7; const int maxn = 20000 + 66; struct Node { int a, b; }; Node aa[maxn]; bool cmp (Node a, Node b) { return a.a < b.a; } int main() { // ifstream cin ("aaa.txt"); int n; cin>> n; for (int i = 1; i <= n; i++) { cin >> aa[i].a >> aa[i].b; } sort (aa + 1, aa + 1 + n, cmp); long long res =0; Node pp = aa[1]; for (int i = 2; i <= n; i++) { if (aa[i].a <= pp.b) { if (aa[i].b > pp.b) pp.b = aa[i].b; } else { res += pp.b - pp.a; pp = aa[i]; } } res += pp.b - pp.a; cout << res << endl; return 0; } |
- « 上一篇：vijos1098
- vijos1312：下一篇 »