目录

• Tallest Cow(差分)
  • 题目
  • 思路
  • 代码

Tallest Cow(差分)

题目

Description

FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 ≤ H ≤ 1,000,000) of the tallest cow along with the index I of that cow.

FJ has made a list of R (0 ≤ R ≤ 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17.

For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.

Input

Line 1: Four space-separated integers: N, I, H and R
Lines 2..R+1: Two distinct space-separated integers A and B (1 ≤ A, B ≤ N), indicating that cow A can see cow B.

Output

Lines 1..N: Line i contains the maximum possible height of cow i.

Sample Input

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

Sample Output

5
4
5
3
4
4
5
5
5

思路

• 题干：一共有 n 头牛 ，给定 这些牛中 最高的那头牛的 高度 和位置（下标） 然后给 r 组数据，每组数据 两个数 ，代表 两头牛之间的牛的高度关系（之间的牛的高度严格小于a） a can see b means the height of a <= the height of b 让求 这些牛 最大的高度

• 因为 a can see b 规定了 a 的上限 是 b所以a 最大就是b的值 假设每头牛 都是 最高高度 H ，通过给定的关系 再根据 高度是整数 所以与他最接近的 就是H-1 ，通过给定的关系 就可以 把给定的两头牛之间的 高度-1 要是遍历的话会变比较麻烦，所以我们想到用差分数组来维护 比较方便 最后再求一下 前缀和 返回 原来高度就可以了

• 差分数组 要手动初始化一下

• 坑点：

• 差分数组 如果不初始化也行 全局变量 就是0 但是要注意 虽然牛 的编号是从1 开始，但是原数组 a 设定告诉为 h时候 要从 0 开始，因为初始化差分数组的时候 b[1]=a[1]-a[0] ,那么 b[1] 就会是 h 元素 都是 0 ，这样在后边 求前缀和会有问题

• 输入 两头牛的编号的时候 x，y的时候，进行操作的时候 会 按照编号的顺序进行操作 （-1，+1的操作），所以当想x>y 的时候 要交换一下数值 另外 如果 x，y同时出现两次 ，那么就会减掉两次，需要查重 用一个二维数组就好了

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int a[N],b[N],vis[N][N];
int n,h,pos,q;
void insertnum(int x,int y)
{
    b[x+1]-=1;
    b[y]+=1;
}

int main()
{
    cin>>n>>pos>>h>>q;
    for(int i=1;i<=n;i++) //就正常 下标 开始就可以了
        a[i]=h;
        for(int i=1;i<n;i++) b[i]=a[i]-a[i-1];
    
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(x>y)  swap(x,y);
        if(vis[x][y])
           continue;
        vis[x][y]=1;
        insertnum(x,y);
        
        
    }

    for(int i=1;i<=n;i++)
    
        a[i]=a[i-1]+b[i];
        
    for(int i=1;i<=n;i++) cout<<a[i]<<endl;

    return 0;
}

// 不初始化
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int a[N],b[N],vis[N][N];
int n,h,pos,q;
void insertnum(int x,int y)
{
    b[x+1]-=1;
    b[y]+=1;
}

int main()
{
    cin>>n>>pos>>h>>q;
    for(int i=0;i<=n;i++)
        a[i]=h;
    
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(x>y)  swap(x,y);
        if(vis[x][y])// 看是不是出现过  坑点 
           continue;
        vis[x][y]=1;
        insertnum(x,y);
        
        
    }

    for(int i=1;i<=n;i++)
    
        a[i]=a[i-1]+b[i];//
        
    for(int i=1;i<=n;i++) cout<<a[i]<<endl;

    return 0;
}