题目描述
有 N 头牛站成一行,被编队为1、2、3…N,每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。
现在,我们只知道其中最高的牛是第 P 头,它的身高是 H ,剩余牛的身高未知。
但是,我们还知道这群牛之中存在着 M 对关系,每对关系都指明了某两头牛 A 和 B 可以相互看见。
求每头牛的身高的最大可能值是多少。
输入格式
第一行输入整数N,P,H,M,数据用空格隔开。
接下来M行,每行输出两个整数 A 和 B ,代表牛 A 和牛 B 可以相互看见,数据用空格隔开。
输出格式
一共输出 N 行数据,每行输出一个整数。
第 i 行输出的整数代表第 i 头牛可能的最大身高。
数据范围
1≤N≤10000,
1≤H≤1000000,
1≤A,B≤10000,
0≤M≤10000
输入样例:
9 3 5 5
1 3
5 3
4 3
3 7
9 8
输出样例:
5
4
5
3
4
4
5
5
5
注意:
此题中给出的关系对可能存在重复
算法分析:
思想:差分
1、默认所有牛的高度是最高的牛的高度
2、建立差分数组height[],由于当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。每有一对关系a和b可以对视,则让[a + 1,b - 1]区域的牛均减一以达到目前最高高度,即height[a + 1] – ; height[b] ++
package 前缀和与差分;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class 最高的牛 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//使用Set记录是否有重复
Set<Integer> set = new HashSet<Integer>();
//输入m总头数,P第几头,H高度,M对关系 以及每一对M关系
int N = scan.nextInt();
int P = scan.nextInt();
int H = scan.nextInt();
int M = scan.nextInt();
//设置一个差分数组
int[] height = new int[N + 10];
//默认全部高度都为最高高度H
height[1] = H;
//输入M对关系
for(int i = 0; i < M;i++)
{
int a = scan.nextInt();
int b = scan.nextInt();
//默认前面的位置是小的
if(a > b) {int t = b; b = a; a = t;}
if(set.contains(a * 20000 + b)) continue;
//让[a + 1,b - 1]区域的牛减一达到目前最高高度
height[a + 1] --; height[b] ++;
set.add(a * 20000 + b);
}
//输出每头牛的最大高度
for(int i = 1;i <= N;i++)
{
height[i] += height[i - 1];
System.out.println(height[i]);
}
}
}