Manchester


私信TA

用户名:wenyajie

访问量:332286

签 名:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

等  级
排  名 1
经  验 65591
参赛次数 1
文章发表 188
年  龄 0
在职情况 学生
学  校 Xiamen University
专  业 计算机科学

  自我简介:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

解题思路:
定义一个数组;数组下标代表数轴上的每个整数点即0,1,2,……,n(长度为500的公路有501颗树);
把这个数组初始化全为1(为1代表有树,0代表被移除);

输入移除区域(x,y),把这个区域上的树全置0;(有多个,用循环控制);

输出为1的树的数目;

注意事项:
数轴上的0点也有数;




参考代码:

#include<stdio.h>
void chushihua(int *a,int n);
void yichu(int *a,int x,int y);
void output(int *a,int n);
void function();
/*--------------------------------------------------*/
int main()
{
  function();
  return 0;
}
/*--------------------------------------------------*/
void function()
{
 int n,h;
 int x,y;
 int a[10001];
 while(scanf("%d%d",&n,&h)!=EOF)
 {
  chushihua(a,n);

  for(int i=0;i<h;i++)
   {scanf("%d%d",&x,&y);yichu(a,x,y);}
   output(a,n);
 }
return ;
}
/*--------------------------------------------------*/
void chushihua(int *a,int n)
{
 for(int i=0;i<=n;i++)
  a[i]=1;
  return ;
}
/*--------------------------------------------------*/
void yichu(int *a,int x,int y)
{
 for(int i=x;i<=y;i++)
  a[i]=0;
  return ;
}
/*--------------------------------------------------*/
void output(int *a,int n)
{
 int sum=0;
 for(int i=0;i<=n;i++)
  {if(a[i]==1)sum++;}

  printf("%d\n",sum);
  return ;
}


 

0.0分

18 人评分

  评论区

思路很重要啊!
2019-01-29 16:41:12
//gcc可以成功,提交时输出超限了,请教大佬帮忙分析一下原因。
#include <stdio.h>
//初始化数组为1 
void InitArray(int *a,int num)
{
	for(int i=0; i<=num; i++)
	{
		a[i]=1;	
	}
}
//将要移除的区域(x,y)置为0 
void InitZero(int *a,int x,int y)
{
	for(int i=x; i<=y; i++)
	{
		a[i]=0;		
	}	
} 
//输出值为1的即为结果 
void Result(int *a,int L)
{	
	int sum=0;
	for(int i=0; i<=L; i++)
	{
		if(a[i]==1)
			sum++;
	}
	printf("%d",sum);
}
int main()
{
	int a[10001]; //题意L<=10000 
	int L,M,x,y;
	while(scanf("%d%d",&L,&M))
	{
		InitArray(a,L);
		for(int i=0; i<M; i++)
		{
			scanf("%d%d",&x,&y);
			InitZero(a,x,y);
		}
			Result(a,L);
	} 
	return 0;
}
2018-12-25 17:02:05
思路很棒,为大佬点赞
2018-12-25 15:48:20
另外一种高效思路是:把重叠的区间去除,得到不重叠的区间,然后再“砍”,上面为了简单省事,就没有考虑重叠部分
2017-12-15 12:52:17