POJ 3617 Best Cow Line ||POJ 3069 Saruman's Army贪心

带来两题贪心算法的题。

1.给定长度为N的字符串S，要构造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下面两个操作：1.从S的头部删除一个字符，加到T的尾部。2.从S的尾部删除一个字符，加到T的尾部。求你任意采取这两个步骤后能得到的最小字符串T

2.直线上有N个点，点i的位置是xi，这N个点中选择若干个做上标记，对于每个点，在他们距离为R的区域内必须带有标记点，求在满足这个条件的情况下，所需要标记点的最少个数。

1.POJ 3617 Best Cow Line

http://poj.org/problem id=3617

题目大意：给定长度为N的字符串S，要构造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下面两个操作：1.从S的头部删除一个字符，加到T的尾部。2.从S的尾部删除一个字符，加到T的尾部。求你任意采取这两个步骤后能得到的最小字符串T

思路：

很容易想到贪心算法，不断的取S的开头和末尾中较小的一个字符放到T的末尾。

很快写完，WA。

因为相等的情况你没有讨论！我们总希望下一个拿到的也是最小的，故要继续比较下一个。

改了然后恶心的PE，80个字母要一个换行。

#include
  
   
#include
   
     #include
    
      const int MAXN=2000+10; char a[MAXN]; int main() { int n; char temp; while(~scanf("%d",&n)) { getchar(); for(int i=0;i
     
      a[n-1]) { printf("%c",a[n-1]); n--; } else //a[i]==a[n-1] { int L=i+1,R=n-2; while(L
      
       
 
       
2.POJ 3069 Saruman's Army
 
       
http://poj.org/problem id=3069
 
 
       
题目大意：
 
       
直线上有N个点，点i的位置是xi，这N个点中选择若干个做上标记，对于每个点，在他们距离为R的区域内必须带有标记点，求在满足这个条件的情况下，所需要标记点的最少个数。
 
       
思路：
 
       
贪心，每次尽量选择向右边的。
 
       

       
#include
        
         
#include
         
           #include
          
            using namespace std; const int MAXN=1000+10; int a[MAXN]; int main() { int n,r; while(scanf("%d%d",&r,&n),n!=-1,r!=-1) { for(int i=0;i
           
            =a[i]) i++; int p=a[i-1]; while(i
            
             =a[i]) i++; ans++; } printf("%d\n",ans); } return 0; }