如何进行企业营销型网站建设,永嘉营销网站建设,网站加载速度,烟台网站制作公司在线咨询0积木 - 蓝桥云课 (lanqiao.cn) 题目描述 小明用积木搭了一个城堡。 为了方便#xff0c;小明在搭的时候用的是一样大小的正方体积木#xff0c;搭在了一个n行m列的方格图上#xff0c;每个积木正好占据方格图的一个小方格。 当然#xff0c;小明的城堡并不是平面的#x…0积木 - 蓝桥云课 (lanqiao.cn) 题目描述 小明用积木搭了一个城堡。 为了方便小明在搭的时候用的是一样大小的正方体积木搭在了一个n行m列的方格图上每个积木正好占据方格图的一个小方格。 当然小明的城堡并不是平面的而是立体的。小明可以将积木垒在别的积木上面。当一个方格上的积木垒得比较高时就是一个高塔当一个方格上没有积木时就是一块平地。 小明的城堡可以用每个方格上垒的积木层数来表示。例如下面就表示一个城堡。 9331 3330 0000 这个城堡南面和东面都有空地西北面有一个大房子在西北角还有一个高塔东北角有一个车库。 现在格格巫要来破坏小明的城堡他施了魔法水淹小明的城堡。 如果水的高度为1则紧贴地面的那些积木要被水淹在上面的例子中有7块积木要被水淹。 如果水的高度为2则更多积木要被水淹在上面的例子中有13块积木要被水淹。 给定小明的城堡图请问水的高度依次为123…H时有多少块积木要被水淹。 输入描述 输入的第一行包含两个整数nm。 接下来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 iostreamusing namespace std;const long long N1e510;
long long n,m,H;
long long diff[N];
long long max1;
long long tmp;int main() {// 请在此输入您的代码cin n m;for(long long i0; in; i) {for(long long j0; jm; j) {long long index;cin index;diff[index];if(max1 index) {max1 index;}}}for(long long i1; imax1; i) {diff[i]diff[i-1];}cin H;for(long long i1; iH; 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 iostreamusing namespace std;const long long N1e510;
long long n,m,H;
long long diff[N];
long long max1;
long long ans;int main()
{// 请在此输入您的代码cin n m;//构造差分for(long long i0; in*m;i){diff[1];long long index;cin index;if(index 1e5)index 1e5;diff[index1]--;}//前缀和for(long long i1;iN;i){diff[i]diff[i-1];}cin H;for(long long i1;iH;i){ans diff[i];cout ans endl;} return 0;
}
