LZH的多重影分身 qduoj 思维差分

原题链接:https://qduoj.com/problem/591

题意

在数轴上有$n$个点（可以重合）和$m$条线段（可以重叠），你可以同时平移这$n$个点，询问最多可以有多少个点在线段上，输出平移的距离$d$，和最后的答案$val$（如果有多个$d$使得$val$最大，则输出最小的$d$）。

解题思路

下面的题解是我们厉害的学长给的，真是太厉害了。

首先，我们用$ans[i]$，来代表平移$i - MAX$（这样表示是因为平移的距离会有负数）的距离会有多少点在线段上。

对于每一个点，我们都可以计算出该点平移到线段上的距离的范围（我们用正数代表向数轴正向移动，用负数代表向数轴负向移动），比如，有一个点位于数轴上$4$的位置，有两条线段$[1,2],[5,6]$，则可以让该点移动到线段上的平移距离的范围为：$[-3,-2],[1,2]$。所以我们可以让$$ans[-3+MAX]...ans[-2+MAX],ans[1+MAX]...ans[2+MAX]$$

各增加1（这不就是区间加的操作吗？）。

这样我们遍历所有的点，就可以得到正确的$ans$数组了。扫描一遍$ans$数组记录最大值即可得到答案。

但是注意：

1.在进行区间加的操作的时候，应该采用差分的方式进行（不能暴力，使用线段树、树状数组等数据结构的时间复杂度也太高，并且相比差分代码量更大）。

2.要先把有交集的线段合并，在统计答案，否则会重复计算。

总结一下就是，求出每个点到达所有的区间所走的长度，然后在这些点上进行加一，这样我们就可以直接进行遍历所有可以走的长度，寻找最大值。学长们真是太强了。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e4+7;

const int maxm=1e3+7;

const int maxlen=1e6+7;

int pos[maxn];

struct Node

{

	int l, r;

	friend bool operator<(const Node a, const Node b)

	{

		return a.l < b.l;

	}

}node[maxm];

int ans[maxlen<<1];

int n, m, cnt;

int main()

{

	scanf("%d%d",&n, &m);

	for(int i=0; i<n; i++)

		scanf("%d", &pos[i]);

	for(int i=0; i<m; i++)

		scanf("%d%d",&node[i].l, &node[i].r);

	sort(node, node+m);

	cnt=1;

	for(int i=1; i<m; i++)

	{

		if(node[cnt-1].r >=node[i].l )

			node[cnt-1].r=max(node[cnt-1].r, node[i].r);

		else

			node[cnt++]=node[i];

	}

	int l, r;

	for(int i=0; i<n; i++)

	{

		for(int j=0; j<cnt; j++)

		{

			l=node[j].l-pos[i]; r=node[j].r-pos[i];

			++ans[l+maxlen];

			--ans[r+maxlen+1];

		}

	}

	int len=maxlen<<1, sum=0, delta=0, outans=0;

	for(int i=0; i<len; i++)

	{

		sum+=ans[i];

		if(sum > outans)

		{

			outans=sum;

			delta=abs(i-maxlen);

		}

		else if(sum==outans && delta > abs(i-maxlen))

		{

			delta=abs(i-maxlen);

		}

	}

	printf("%d %d\n", delta, outans);

	return 0;

 }

巴特西

LZH的多重影分身 qduoj 思维差分

LZH的多重影分身 qduoj 思维差分

题意

解题思路

代码实现

最新文章

热门文章

巴特西

LZH的多重影分身 qduoj 思维 差分

LZH的多重影分身 qduoj 思维 差分

题意

解题思路

代码实现

最新文章

热门文章

LZH的多重影分身 qduoj 思维差分

LZH的多重影分身 qduoj 思维差分