题目背景

编程俱乐部即将参加程序设计大赛，在参加之前，男神丁建议大家一起合一个影。

题目描述

在比赛赛后男神丁给大家提出了一个问题，现在，你只知道俱乐部中最高的人的身高是H,在位置P上，并且给出你们n对关系，(a,b)表示a、b位置上的人可以互相看见（当且仅当他们中间的人都比他们矮时才能互相看到），求照片上每个人的最大身高可能是多少。

输入格式：

第一行输入整数N,P,H,M，

接下来M行，每行两个整数 A 和 B ，代表位置A 和位置B上的人可以互相看见

输出格式：

一共输出 N 行数据，每行输出一个整数。

第 i 行输出的整数代表第 i 个位置上的人可能的最大身高是多少。

输入样例#1：

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例#1：

5
4
5
3
4
4
5
5
5

说明

1≤N≤10000,
1≤H≤1000000,
1≤A,B≤10000,
0≤M≤10000

思路

这个题我开始用的模拟，但被一组数据卡住了，不得已才用的差分。

代码

#include
int l[10005]={0},N,P,H,R,A,B;
int arr[10005][10005];     //记录是否有重复数据。
int main()
{scanf("%d%d%d%d",&N,&P,&H,&R);while(R--){scanf("%d%d",&A,&B);if(A>B)       //保证A>B。{int z=A;A=B;B=z;}if(arr[A][B])       //如果输入数据重复，continue。continue;else            //如果不重复，差分{l[A+1]--;l[B]++;arr[A][B]=true;}}for(int i=1;i<=N;i++){l[i]+=l[i-1];printf("%d\n",l[i]+H);}return 0;
}

加上大佬对差分的解释

差分

差分就是将数列中的每一项分别与前一项数做差，例如：

一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3

这里注意得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0）

差分序列最后比原序列多一个数（相当于0减最后一个数）

性质：

1、差分序列求前缀和可得原序列

2、将原序列区间[L,R]中的元素全部+1，可以转化操作为差分序列L处+1，R+1处-1

3、按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！