校门外的树WriteUp
原题链接:
AC源代码:
暴力做法:
时间复杂度O(M*N)
#include <iostream>
using namespace std;
int main()
{
int l , m, res = 0;
cin >> l >> m;
bool a[l + 1] ;
for ( int i = 0 ; i < l + 1 ; i ++) a[i] = true;
while ( m --)
{
int x, y;
cin >> x >> y;
for ( int i = x ; i <= y ; i ++) a[i] = false;
}
for ( int i = 0 ; i < l + 1 ; i ++)
if ( a[i]) res ++;
cout << res << endl;
return 0;
}
区间合并做法(利用pair)
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int , int > PII;
PII a[101];
int main()
{
int l , m;
cin >> l >> m;
for ( int i = 0 ; i < m; i ++) cin >> a[i].first >> a[i].second;
sort(a, a + m);
int st = a[0].first , ed = a[0].second;
for ( int i = 0 ; i < m; i ++)
{
if ( a[i].first <= ed ) ed = max(ed, a[i].second);
else
{
l = l - ( ed - st + 1);
st = a[i].first;
ed = a[i].second;
}
}
l -= ed - st + 1;
cout << l + 1 << endl; //l米长度的公路上一共有l + 1棵树。
return 0;
}
区间合并做法(结构体)
以下代码摘自YXC
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int m, n;
struct Segment
{
int l, r;
bool operator< (const Segment& t) const
{
return l < t.l;
}
}seg[N];
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> seg[i].l >> seg[i].r;
sort(seg, seg + n);
int sum = 0;
int L = seg[0].l, R = seg[0].r;
for (int i = 1; i < n; i ++ )
if (seg[i].l <= R) R = max(R, seg[i].r);
else
{
sum += R - L + 1;
L = seg[i].l, R = seg[i].r;
}
sum += R - L + 1;
cout << m + 1 - sum << endl;
return 0;
}