每次选取在所有区间中出现次数最多的数字 结果总是wa
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
int a[10001];
int b[10001];
int c[10001];
int yong[10001];
int main()
{ int n;
  scanf("%d",&n);
  int sum;
  memset(yong,0,sizeof(yong));
  memset(c,0,sizeof(c));
  int i,j;
  int max1=-1,min1=10001;
  int max,maxi;
  for(i=0;i<n;i++)
  {scanf("%d%d",&a[i],&b[i]);
   for(j=a[i];j<=b[i];j++)
   yong[j]++;
  }
  sum=0;
  int biaozhi=0;
  while(biaozhi!=n)
  {   max=0;
	  for(i=0;i<=10000;i++)
	  if(yong[i]>max) {max=yong[i],maxi=i;}
	  yong[maxi]=-1;
	  sum++;
	  for(i=0;i<n;i++)
	  if(c[i]<2&&maxi>=a[i]&&maxi<=b[i]) 
	  {c[i]++;
       if(c[i]==2) 
	   {biaozhi++;
		for(j=a[i];j<=b[i];j++)
        yong[j]--;}
	  }
  }
  printf("%d\n",sum);
  return 0;
  
}

• 贪心策略不对~ (877) ysg860607 2008-09-20 01:27:04