Tallest Cow POJ - 3263 差分前缀和

程序员文章站 2022-07-12 17:39:19

...

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头牛，第i头牛是最高的，高度为H，现在给出r对牛之间的关系，

牛1可以看到牛3，说明牛2一定小于牛1.牛3是<=牛1；

要求求出n头牛的最大的高度。（当然给出的关系可能会有重复的，所以要去重）

普通-两层循环

#include<iostream>
#include<cstdio>
#include<set>
#include<string>
#include<cstring>
#include<sstream>
#include<cmath>
#include<algorithm>
using namespace std;
set<string> que;
int c[10077];
int main()
{
    int n,i,h,r;
    int a,b,mina,maxb;
    string s = "";
    scanf("%d%d%d%d", &n,&i,&h,&r);
    memset(c,0,sizeof(c));
    for(int i = 0; i < r; i++)
    {
        scanf("%d%d", &a, &b);
        mina = min(a,b);
        maxb = max(a,b);
        stringstream ss;
        ss << mina;
        ss << maxb;
        ss >> s; 
        if(que.count(s)) //通过set来判断给出的关系不能有重复的
        {
            continue;
        }
        for(int j = mina + 1; j < maxb; j++)//将a和b之间的牛的高度都减少
            c[j]--;
        que.insert(s);

    }
    for(int i = 1; i <= n; i++)
    {
        printf("%d\n", c[i]+h);
    }
    return 0;
}

差分计算前缀和

定义：即为数组的每一项存储的是数列的每一项与其前一项的差值。

设有一数列d，那么d的差分数组f中：f[1]=d[1];对于整数i∈[2,n]，f[i]=d[i]-d[i-1];

性质：

（1）：通过差分数组f来求数列d各项的值：

d[2] = f[2]+f[1] = d[2]-d[1]+d[1] = d[2] 即 d[i] 为f[i]的前缀和

应用：

（1）：快速区间加减

要将区间[1,3]之间的值都+3

d[1] = f[1] + 3;

d[2] = f[1] + 3 + f[2];

d[3] = f[1] + 3 + f[2] + f[3];

d[4] = f[1] + 3 + f[2] + f[3] + f[4] - 3;

可以发现使用差分数组，当f[1]+3后，后面数列元素在计算过程中都会加上3；最后一个受影响的差分数组中的元素为f[3],所以令f[3+1]-3，即可保证不会影响到3以后数列元素的计算。这样我们不必对区间[1,3]内每一个数进行处理，只需处理两个边界的差分值即可；

那么这个题，使所有的牛初始高度都为0，那么差分数组f的初始也都为0，就可以直接对牛a+1高度-1，牛b的高度+1，最后求出d数列，输出时每项+h即可

#include<iostream>
#include<cstdio>
#include<set>
#include<string>
#include<sstream>
#include<cmath>
#include<algorithm>
using namespace std;
set<string> que;
int d[10077],f[10077];
int main()
{
    int n,i,h,r;
    int a,b,mina,maxb;
    string s = "";
    scanf("%d%d%d%d", &n,&i,&h,&r);
    for(int i = 0; i < r; i++)
    {
        scanf("%d%d", &a, &b);
        mina = min(a,b);
        maxb = max(a,b);
        stringstream ss;
        ss << mina;
        ss << maxb;
        ss >> s;
        if(que.count(s))
        {
            continue;
        } 
        f[mina + 1]--;
        f[maxb]++;
        que.insert(s);

    }
    for(int i = 1; i <= n; i++)
    {
        d[i] = d[i - 1] + f[i];
        printf("%d\n", d[i]+h);
    }
    return 0;
}