生活随笔
收集整理的這篇文章主要介紹了
7620:区间合并
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
7620:區間合并
總時間限制:
1000ms內存限制:
65536kB描述
給定 n 個閉區間 [ai; bi]，其中i=1,2,...,n。任意兩個相鄰或相交的閉區間可以合并為一個閉區間。例如，[1;2] 和 [2;3] 可以合并為 [1;3]，[1;3] 和 [2;4] 可以合并為 [1;4]，但是[1;2] 和 [3;4] 不可以合并。
我們的任務是判斷這些區間是否可以最終合并為一個閉區間，如果可以，將這個閉區間輸出，否則輸出no。
輸入
第一行為一個整數n，3 ≤ n ≤ 50000。表示輸入區間的數量。
之后n行，在第i行上（1 ≤ i ≤ n），為兩個整數 ai 和 bi ，整數之間用一個空格分隔，表示區間 [ai; bi]（其中 1 ≤ ai ≤ bi ≤ 10000）。輸出
輸出一行，如果這些區間最終可以合并為一個閉區間，輸出這個閉區間的左右邊界，用單個空格隔開；否則輸出 no。樣例輸入
5
5 6
1 5
10 10
6 9
8 10 樣例輸出
1 10 來源
1 #include<iostream>
2 #include<cmath>
3 using namespace std;
4 int ansbegin=
10000;
5 int ansend=-
1;
6 int beginn[
1000001];
7 int endn[
1000001];
8 int flag[
10000001];
9 int main()
10 {
11 int n;
12 cin>>
n;
13 for(
int i=
1;i<=n;i++
)
14 {
15 cin>>beginn[i]>>
endn[i];
16 if(beginn[i]<
ansbegin)
17 ansbegin=
beginn[i];
18 if(endn[i]>
ansend)
19 ansend=
endn[i];
20 for(
int j=beginn[i]*
2;j<=endn[i]*
2;j++
)
21 {
22 flag[j]=
1;
23 }
24 }
25 for(
int i=ansbegin*
2;i<=ansend*
2;i++
)
26 {
27 if(flag[i]==
0)
28 {
29 cout<<
"no";
30 return 0;
31 }
32 }
33 cout<<ansbegin<<
' '<<
ansend;
34 return 0;
35 }
?
轉載于:https://www.cnblogs.com/zwfymqz/p/6613401.html
總結
以上是生活随笔為你收集整理的7620:区间合并的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
