华师一附中OI组

标题: P1496 火烧赤壁 [打印本页]

---

作者: admin    时间: 2018-7-3 16:45
标题: P1496 火烧赤壁
https://www.luogu.org/problemnew/show/P1496

题目描述
曹操平定北方以后，公元208年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。

隆冬的十一月，天气突然回暖，刮起了东南风。

没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。

曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！

输入输出格式
输入格式：
第一行：N

以后N行，每行两个数：Ai Bi(表示连环线上着火船只的起始位置和终点,-10^9<=Ai,Bi<=10^9)

输出格式：
输出着火船只的总长度

输入输出样例
输入样例#1：
3
-1 1
5 11
2 9
输出样例#1：
11
说明
n<=20000

如果Ai=Bi是一个点则看作没有长度

---

作者: 倚窗倾听风吹雨    时间: 2018-7-6 13:54

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. struct q
   
5. {
   
6.     int s,e;
   
7. }a[20010];
   
8. int i,n,be,en,sum;
   
9. bool cmp(q x,q y)
   
10. {
    
11.     return x.s<y.s;
    
12. }
    
13. int main()
    
14. {
    
15.     cin>>n;
    
16.     for(i=1;i<=n;i++)
    
17.         cin>>a[i].s>>a[i].e;
    
18.     sort(a+1,a+n+1,cmp);
    
19.     be=a[1].s;
    
20.     en=a[1].e;
    
21.     sum=en-be;
    
22.     for(i=2;i<=n;i++)
    
23.     {
    
24.          if(a[i].s<=en)
    
25.         {
    
26.             if(a[i].e<en) continue;
    
27.             else
    
28.             {
    
29.                 be=en;
    
30.                 en=a[i].e;
    
31.                 sum+=en-be;
    
32.             }
    
33.         }
    
34.         else
    
35.         {
    
36.             be=a[i].s;
    
37.             en=a[i].e;
    
38.             sum+=en-be;
    
39.         }
    
40.     }
    
41.     cout<<sum;
    
42.     return 0;
    
43. }

复制代码

---

作者: 吴语林    时间: 2018-7-29 20:57

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. struct bla
    
14. {
    
15.         int q,z;
    
16. }a[21000];
    
17. int n,all=0;
    
18. bool cmp(bla x,bla y)
    
19. {
    
20.         return x.q<y.q;
    
21. }
    
22. int main()
    
23. {
    
24.         scanf("%d",&n);
    
25.         for(int i=1;i<=n;i++)
    
26.                 scanf("%d%d",&a[i].q,&a[i].z);
    
27.         sort(a+1,a+1+n,cmp);
    
28.         int qi=a[1].q,zh=a[1].z;
    
29.         for(int i=2;i<=n;i++)
    
30.         {
    
31.                 if(a[i].q>zh)
    
32.                         all+=zh-qi,qi=a[i].q,zh=a[i].z;
    
33.                 else
    
34.                         zh=max(zh,a[i].z);
    
35.         }
    
36.         printf("%d",all+zh-qi);
    
37.         return 0;
    
38. }

复制代码

---

作者: 黄煦喆    时间: 2018-8-30 21:57

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,s,e;
   
5. long long ans;
   
6. struct ll
   
7. {
   
8.     int x,y;
   
9. } l[20001];
   
10. bool operator< (ll A,ll B)
    
11. {
    
12.     return A.x<B.x;
    
13. }
    
14. int main()
    
15. {
    
16.     cin>>n;
    
17.     for(int i=1; i<=n; i++)cin>>l[i].x>>l[i].y;
    
18.     sort(l+1,l+n+1);
    
19.     s=l[1].x,e=l[1].y;
    
20.     ans=e-s;
    
21.     for(int i=2; i<=n; i++)
    
22.         if(l[i].x<=e)
    
23.         {
    
24.             if(l[i].y>=e)
    
25.             {
    
26.                 s=e;
    
27.                 e=l[i].y;
    
28.                 ans+=e-s;
    
29.             }
    
30.         }
    
31.         else
    
32.         {
    
33.             s=l[i].x,e=l[i].y;
    
34.             ans+=e-s;
    
35.         }
    
36.     cout<<ans;
    
37.     return 0;
    
38. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2