試題 演算法訓練 藏匿的刺客
資源限制
時間限制：1.0s 記憶體限制：256.0MB
問題描述
強大的kAc建立了強大的帝國，但人民深受其學霸及23文化的壓迫，于是勇敢的鵬決心反抗，
kAc帝國防守森嚴，鵬帶領著小伙伴們躲在城外的草堆葉子中，稱為葉子鵬，
kAc帝國的派出的n個看守員都發現了這一問題，第i個人會告訴你在第li個草堆到第ri個草堆里面有人，要求你計算所有草堆中最少的人數，以商議應對，
“你為什么這么厲害”，得到過kAc衷心贊美的你必將全力以赴，
輸入格式
第一行兩個整數N,M，
一行N個整數，表示木棍的長度，
輸出格式
輸出一個數，表示最少人數，
樣例輸入
5
2 4
1 3
5 7
1 8
8 8
樣例輸出
3
資料規模和約定
30%的資料n<=10
70%的資料n<=100
100%的資料n<=1000
所有數字均在int表示范圍內
思路：
-
將每個區間按右端點排序
-
將最小的右端點和下一個區間的左端點比較，若左端點小于右端點，說明兩區間重合，只要在該右端點記一個人即可
-
若左端點大于右端點，說明兩區間未重合，需要再記一個人，并且更新最小右端點為該區間的右端點
-
遍歷所有區間
要點：
- 排序
- 記最多的區間能重合的點
代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct Range{
int l , r;
bool operator<(const Range &w) const{
return r < w.r;
}
}range[N];
int n;
int main(){
cin >> n;
for (int i = 0 ; i < n ; i ++ )
cin >> range[i].l >> range[i].r;
sort(range, range + n);
int minr = range[0].r;
int res = 1;
for (int i = 1; i < n ; i ++)
if (range[i].l > minr){
res ++;
minr = range[i].r;
}
cout << res << endl;
return 0;
}
吐槽：
none
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/428501.html
標籤：其他
上一篇：Sonar 掃描之分析引數介紹
下一篇：演算法基礎知識總結