时间戳

首页 > 技术文章 > zoj 3197 Google Book

zoj 3197 Google Book

woshijishu3 2014-03-16 00:12 原文

这道题告诉我想法正确是多么重要，先是我自己想的时候没考虑到最后的页码作为循环的终止，我一直以区间个数来终止循环，这是多么愚蠢啊！然后，我看了别人的代码，但是很不幸超时了！

我自己wa的代码，我感觉很正确就是对不了！



#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
	return (*(int *)a-*(int *)b);
}

int main(void)
{
	int t,n,i,j,count,k,temp;
	int s[5002][2];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
		scanf("%d%d",&s[i][0],&s[i][1]);
		qsort(s,n,sizeof(s[0]),cmp); 
		count=0;
		for(i=0,k=1;i<n&&k<n;)
		{
			if(s[i][1]>=s[k][1])/*盖住后面的 */
			{
				k++;
				count++;
			}
			else if(s[i][0]==s[k][0]&&s[i][1]<=s[k][1])/*被后面盖住 */
			{
				/*如果i被k盖住，说明中间的全部被覆盖了*/ 
				i=k;/*k后移一位，i移到k位置*/
				k++;
				count++;
			}
			else 
			{
				i=k;/*k后移一位，i移到k位置*/
				k++;
			}
		}
		printf("%d\n",n-count);
		
	} 
	return 0;
}


 




然后我就看网上的算法，然后改了，不过居然超时了




#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return (*(int *)a-*(int *)b);
}
int s[5001][2];
int main(void)
{
    int t,n,i,j,count,k,temp,end,sta,sum,ma;
    
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        
        for(i=0;i<n;i++)
        scanf("%d%d",&s[i][0],&s[i][1]);
        
        qsort(s,n,sizeof(s[0]),cmp); 
        ma=0;
        end = s[0][1],sta = s[0][0];/*得到比较的开始，和结束地址 */
         sum = 1;/*区间个数从1开始 */
        i = 1;          
         while(i<n && s[i][0]  == sta)/*找到以1为开始区间群中最大那一页页码 */         
         {         
             if(end < s[i][1]) {             
                      end = s[i][1];        
                     ma=i;         
                     }     ;
                    i++;      
                  }
                  while(end!=n)/*当找到的页码等于最后的页码就可以停止循环 */
                  {
                      j=s[ma][1];/*得到当前以i为开始区间群中最大的页码 */
                          sta = end+1;/*查找的页码从上一个区间群中的最后一个开始 */
                          i++;/*获取当前区间群的第一个 */
                          while(i<n && s[i][0] <= sta)/*找打这个区间群中最大的 j*/    
                          {
                                  if(s[i][1] > j) 
                                  {
                                      j = s[i][1];
                                      ma=i;
                                  }
                                  i++;
                          }
                          if(j > end)/*如果区间群中最大的大于上一个区间群的最大，那么就需要增加一个了 */
                          {
                                 sum++;
                                 end = j;
                          }
                  }
                  printf("%d\n",sum);
        
    } 
    return 0;
}




最后实在没办法了，只能再找了，终于看到了一个最ok的了，就是在已经排好的区间中找多少个尾部递增序列，很轻松的解决了这题，我靠怎么都没想过这种方法！想法正确真的很重要




#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return (*(int *)a-*(int *)b);
}
int s[5001][2];
int main(void)
{
    int t,n,i,j,end,sta,sum,p,max;
    
    scanf("%d",&t);
    
   while(t--)
    {
        scanf("%d",&end);/*最后的页码号*/
        
        for(i=0;i<end;++i)
        {
            scanf("%d %d",&s[i][0],&s[i][1]);
        }
        
        qsort(s,end,sizeof(s[0]),cmp);
        
        n=0 ;
        p=0 ;
        sum=1 ;
        
        while(sum<=end)
        {
            
            max=-1 ;/*每一次求新递增序列的最大值，这个值就需要初始化*/
            
            for(i=p;i<end;++i)/*循环页码区间，找到连续递增最大的页码*/ 
            {
                if(s[i][0]<=sum)
                {
                    if((s[i][1]>=sum)&&(s[i][1]>max))/*更新最大的页码*/
                    {
                        max=s[i][1] ;
                    }
                }
                else /*如果页码递减就跳出*/
                 break ;
            }
            
            sum=max+1 ;/*在后面递增区间中找出比前一个递增最大值，大1的页码*/ 
            p=i ;/*跳到最大区间后面*/ 
            ++n ;/*每一次找新递增序列的最大，就代表前面序列区间内查最大的就可以了，所以加1*/ 
        }
        
        printf("%d\n",n);
        
    } 
    return 0;
}




 







	

		


推荐阅读