0积木 - 蓝桥云课 (lanqiao.cn)
题目描述
小明用积木搭了一个城堡。
为了方便，小明在搭的时候用的是一样大小的正方体积木，搭在了一个n行m列的方格图上，每个积木正好占据方格图的一个小方格。
当然，小明的城堡并不是平面的，而是立体的。小明可以将积木垒在别的积木上面。当一个方格上的积木垒得比较高时，就是一个高塔，当一个方格上没有积木时，就是一块平地。
小明的城堡可以用每个方格上垒的积木层数来表示。例如，下面就表示一个城堡。
9331
3330
0000
这个城堡南面和东面都有空地，西北面有一个大房子，在西北角还有一个高塔，东北角有一个车库。
现在，格格巫要来破坏小明的城堡，他施了魔法水淹小明的城堡。
如果水的高度为1，则紧贴地面的那些积木要被水淹，在上面的例子中，有7块积木要被水淹。
如果水的高度为2，则更多积木要被水淹，在上面的例子中，有13块积木要被水淹。
给定小明的城堡图，请问，水的高度依次为1，2，3，…，H时，有多少块积木要被水淹。
输入描述
输入的第一行包含两个整数n，m。
接下来n行，每行m个整数，表示小明的城堡中每个位置积木的层数。
接下来包含一个整数H，表示水高度的上限。
其中，便积木层数不超过1e9
输出描述
输出H行，每行一个整数。第i行的整数表示水的高度为i时被水淹的积木数量。输入输出样例
输入
3 4
9 3 3 1
3 3 3 0
0 0 0 0
10
输出
7
13
19
20
21
22
23
24
25
25
#include <iostream>using namespace std;const long long N=1e5+10;
long long n,m,H;
long long diff[N];
long long max1;
long long tmp;int main() {// 请在此输入您的代码cin >> n >> m;for(long long i=0; i<n; i++) {for(long long j=0; j<m; j++) {long long index;cin >> index;diff[index]++;if(max1 < index) {max1 = index;}}}for(long long i=1; i<=max1; i++) {diff[i]+=diff[i-1];}cin >> H;for(long long i=1; i<=H; i++) {tmp += diff[max1] - diff[i-1];cout << tmp << endl;}return 0;
}
思考：
long long diff [ 1e9 + 10]会编译失败，退了一步 写 diff [ 1e5 + 10] ，当输入大于1e5时，处理为1e5，因为水位最大到1e5；以下代码只能过50%，应该是在前缀和的时候爆了，需要优化一下前缀和
优化：
先差分，再前缀和
#include <iostream>using namespace std;const long long N=1e5+10;
long long n,m,H;
long long diff[N];
long long max1;
long long ans;int main()
{// 请在此输入您的代码cin >> n >> m;//构造差分for(long long i=0; i<n*m;i++){diff[1]++;long long index;cin >> index;if(index > 1e5)index = 1e5;diff[index+1]--;}//前缀和for(long long i=1;i<=N;i++){diff[i]+=diff[i-1];}cin >> H;for(long long i=1;i<=H;i++){ans += diff[i];cout << ans << endl;} return 0;
}
