LZH的多重影分身 qduoj 思维 差分 LZH的多重影分身 qduoj 思维 差分
题意
在数轴上有(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
", delta, outans);
return 0;
}