树状数组算法 - 凌冬的个人博客

有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。

现在这 nn 头奶牛站成一列，已知第 ii 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。

输入格式

第 11 行：输入整数 n

第 2..n 行：每行输入一个整数 Ai ，第 ii 行表示第 ii 头牛前面有 Ai 头牛比它低。（注意：因为第 11 头牛前面没有牛，所以并没有将它列出）

输出格式

输出包含 n 行，每行输出一个整数表示牛的身高。

第 i 行输出第 i 头牛的身高。

数据范围

$1≤n≤10^5 $

输入样例：

输出样例：

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


#include <bits/stdc++.h>
using namespace std;

int lowbit(int x)  // 返回末尾的1
{
    return x & -x;
}

const int N =  1e5+10;
int tr[N],n;
void add(int u,int f) {
    for(int i=u;i<=n; i+=lowbit(i)) tr[i] += f;
    
}
int sum(int u) {
    int res=0;
    for(int t=u;t>=1;t-=lowbit(t)) res += tr[t] ;
    return res;
 
}

int A[N];
int ans[N],ans_cnt;
int main(void) {
    
    cin>>n;
    for(int i=2;i<=n;++i) {
        cin>>A[i];
        //add(i,1);
    }
    for(int i=1;i<=n;++i) {
        //tr[i] = lowbit(i);
    
        add(i,1);
    }
    
    for(int i=n;i>=1;--i) {
        int k = A[i] + 1;
        int l=1,r=n;
        while(l<r) {
            int midh = l+r>>1;
            if(sum(midh) >=k) {
                r = midh;
            }else l=midh+1;
        }
        //找到 一个 最少的 h，是的 sum[x] == k,有 k个数 的高度都是 小于 h
        ans[i] = r;
        add(r,-1);//减去这个 高度为 h的数
    }
    for(int i=1;i<=n;++i) 
        printf("%d\n",ans[i]);
    
    
    
    return 0;
}

差分算法

1109. 航班预订统计

Difficulty: 中等

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 1：

1
2
3
4
5
6
7
8
9


输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

1
2
3
4
5
6
7
8


输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

提示：

1 <= n <= 2 * 104
1 <= bookings.length <= 2 * 104
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 104

Solution

Language: ****

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
public:
    vector<int> help;
    #define lowbit(x) (x&-x)
    void add(int x,int c) {
        for(int i=x;i<help.size();i+= lowbit(i) ) help[i] += c;
    }
    int query(int x) {
        int res=0;
        for(int i=x;i;i-=lowbit(i) )
            res += help[i];
        return res;
    }
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        //res = vector<int> (n,0);
        //a[l] += c,  a[r+1] -= c;
        // res = sum[l,r]
        help = vector<int> (n+1,0);
        for (auto item : bookings) {
            int u = item[0] , v= item[1],w = item[2];
            add(u,w),add(v+1,-w);
        }
        vector<int> res;
        for(int i=0;i<n;++i) {
            res.push_back(  query(i+1) -0 );
        }
        return res;
    }
};

差分解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
 
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
       
        vector<int> b(n);
        for(auto item: bookings) {
            int u = item[0],
                v = item[1],
                w = item[2];
            b[u-1] += w;
            if(v<n) b[v] -= w;
        }
        //vector<int> res;
        for(int i=1;i<n;++i) 
        {
            b[i] += b[i-1];
        }

        return b;
        


    }





};

文章目录