Question

编程 校门外的树

题目描述
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是一米，我们可以把马路看成一个数轴，马路的一端在零的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2……L，都种有一棵树。由于马路上有一些区域要用来修地铁，这些区域用他们在数轴上的起始点和终止点表示。已知任意区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树)移走。

输入描述
输入的第一行有两个整数L（1<=L<=10000),和M(1<=M<=100),L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出描述
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

输入样例
500 3
150 300
100 200
470 471

输出样例
298

#include<iostream>
using namespace std ;

int main()
{
int i , j , L , M , left ;
int a[1000] , b[1000] ;
cin >> L >> M ;

for( i = 0 ; i < M ; i ++ )
{
cin >> a[i] >> b[i] ;
}

for( i = 0 ; i < M - 1 ; i ++ )
{
int t , k ;
for( j = 0 ; j < M - 1 - i ; j ++ )
{
if( a[j] > a[j+1] )
{
t = a[j] ;
k = b[j] ;
a[j] = a[j+1] ;
b[j] = b[j+1] ;
a[j+1] = t ;
b[j+1] = k ;
}
}
}
left = a[0] ;

for( i = 0 ; i < M ; i ++ )
{
int max = 0 , flag = 1 ;;
for( j = 0 ; j < i ; j ++ )
{
if( b[j] > a[i] )
{
flag = 0 ;
break ;
}
else
{

if( b[j] > max )
max = b[j] ;
}
}
if( flag == 1 )
{
left += a[i] - max ;
}

}
left += L - b[M-1] ;
cout << left << endl ;
return 0 ;
}
帮我看看我的算法哪里错了 。。。。谢谢。。。。。

Answer 1

贪心吧。

很久木有做算法题目了，看不下去。

追问

那就算了 。。。 我也不想把简单的复杂化了 就用简单的方法了。。不用看了

Answer 2

对