校门外的树-19行代码-时间复杂度O(n) !

谢雨辰 2年前 回复TA

为什么有一个样例出错了
#include<iostream>
using namespace std;

int main()
{
	int m,n,ans=0;
	int arr[101][2];
	cin>>m>>n; 
	int ch[10000]={0}; 
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<2;j++)
		{
			cin>>arr[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		
		for(int j=arr[i][0]-1;j<arr[i][1];j++)
		{
			ch[j]=1;
		}		
	}
	for(int i=0;i<m;i++)
	{
		if(ch[i]==1)
		{
			ans++;
		}
	}
	cout<<m-ans+1;	
}

悠游 2年前 回复TA

@黑云 以L作为数组长度，这思路不错呀，然后把数组的元素序号作为数轴，一开始的所有元素为1，被被移走的树的序号所在元素为0，然后统计元素值为1的元素数，就为剩下的树的数，好好好，好思路，不过你是想缩小运算量吗

蝶翅 2年前 回复TA

#include<stdio.h>
int main()
{
	int diff = 0, ans = 0;
	int l, m;
	scanf("%d%d", &l, &m);
	int tree[10007] = {};
	while(m -- ) {
	    int x, y;
	    scanf("%d%d", &x, &y);
	    tree[x] ++ ;
	    tree[y + 1] -- ;
	}
	
	for (int i = 0; i <= l; i ++ ) {
	    diff += tree[i];
	    if (diff == 0) ans ++ ;
	}
	
	printf("%d", ans);
	return 0;
}

差分这样写更好一点

蝶翅 2年前 回复TA

差分，不错

琢靖 3年前 回复TA

这种方法太妙了，先记下来，我也想学会这种算法思想！理解运用！

doct.黄 3年前 回复TA

秒啊

黑云 3年前 回复TA

测试答案错一小半，感觉没错，不知道是哪里没住要到
#include<stdio.h>
int main(void)
{
	int L, M;
	scanf("%d", &L);
	scanf("%d", &M);
	int a[L+1];
	int i, x, y, ans = 0, fornt, last, k = 0;
	for(i=0; i<=L; i++)
	{
		a[i] = 0;
	 } 
	 for(i=1; i<=M; i++)
	 {
	 	scanf("%d%d", &x, &y);
	 	a[x] = 1; 
	 	a[y] = -1;
	 }
	 for(i=0; i<=L; i++)
	 {
	 	if(a[i] == 1)
	 	{
	 		k++;
		 }
		 if(a[i] == -1)
		 {
		 	k--;
		 }
		 if(a[i]==0 && k==0)
		 {
		 	ans++;
		 }
	 }
	 printf("%d\n", ans);
	 return 0;
}

Shai 3年前 回复TA

秒啊

linmanba 3年前 回复TA

为啥答案错误？但是结果是正确的
#include <stdio.h>
int main()
{
	int len,m,sum;
	scanf("%d %d",&len,&m);
	int a[100001];
	for(int i=0;i<=len;i++)
	{
		a[i]=1;
	}
	int b[100][2];
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<2;j++)
		{
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<m;i++)
	{
		for(int j=b[i][0];j<=b[i][1];j++)
		{
			a[j]=0;
		}
	}
	for(int i=0;i<=len;i++)
	{
		if(a[i]==1)
		sum++;
	}
	printf("%d",sum);
	return 0;
}

chuashifengz 3年前 回复TA

这是啥思想啊?膜拜大佬!

发表评论 取消回复