萌新初学离散化,20pts求助QAQ
查看原帖
萌新初学离散化,20pts求助QAQ
587819
gzkeylucky楼主2022/7/19 19:06

根据题解中的离散化思路做的,但不知道哪里有问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=1e8+5;
int c[maxn],n,cnt=0;
struct node{
	int x,y;
}edge[maxn];
bool vis[maxn];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

int main()
{
	int sum=0;
	memset(vis,false,sizeof(vis));
	n=read();
	for(int i=1;i<=n;++i)
	{
		edge[i].x=read();
		edge[i].y=read();
		c[++cnt]=edge[i].x;
		c[++cnt]=edge[i].y;
	}
	sort(c+1,c+cnt+1);
	for(int i=1;i<=n;++i)
	{
		for(int j=edge[i].x;j<=edge[i].y;++j)
		{
			vis[j]=true;
		}
	}
	for(int i=1;i<=cnt;++i)
	{
		if(vis[i])
		sum+=c[i]-c[i-1];
	}
	cout<<sum;
	
	return 0;
}
2022/7/19 19:06
加载中...