#include<iostream>
#include<cstdlib>
using namespace std;
int MIN;
struct P
{
int b;
int e;
int visited;
}arr[10000];
int comp(const void *arg1, const void *arg2)
{
return (*(struct P *)arg1).e < (*(struct P *)arg2).e;
}
void func(int LEN,int N,int i,int sb)//LEN是最右邊那個點，N是界限，i是開始支持的點，Nsb是次數
{
MIN=sb;
int start=LEN;
if(LEN>0)
{
while(i<N)
{
if(arr[i].e<LEN)break;
else
{
if(arr[i].b<start)
start=arr[i].b;
}
i++;
}
func(start,N,i,sb+1);
}
}
int main()
{
//freopen("s.txt","r",stdin);
//freopen("key.txt","w",stdout);
int LEN,N,j,temp1,temp2;
cin>>LEN>>N;
while(LEN!=0)
{
MIN=10000;
for(j=0;j<N;j++)
{
cin>>temp1>>temp2;
arr[j].b=temp1-temp2;
arr[j].e=temp1+temp2;
}
qsort(arr, N, sizeof(arr[0]), comp);
func(LEN,N,0,0);
cout<<MIN<<endl;
cin>>LEN>>N;
}
//system("PAUSE");
return 0;
}
posted on 2009-05-16 11:41
luis 閱讀(255)
評論(0) 編輯 收藏 引用 所屬分類:
貪心*二分