bzoj-2957 楼房重建

题意：

数轴上有n个楼，分别在1~n这些点上；

m次查询。每次改变一个楼的高度，问从(0,0)这个点能够看到多少楼；

题解：
对于一个楼来说要想看到这个楼。那么前面的楼的斜率一定比这个楼小；

那么考虑分块的话。就将块中楼的斜率都求出来。

然后维护出一个从块首元素開始的递增序列；

即包含块首元素的下标最小的序列；

扫一遍全部块。取该块之前的全部楼的最大斜率为ma；

在当前块中二分找比ma大的元素个数。并更新ma。

复杂度O(m*√n*log(√n))，时间基本和1s擦边；

可是BZ算的总时限全部能够无压力AC。

代码：

#include<math.h> #include<stdio.h> #include<string.h> #include<algorithm> #define N 110001 using namespace std; int bk, h[N], cnt[400]; double k[N], q[400][400]; int main() {int n, m, i, j, index, x, y, ans;double ma;scanf("%d%d", &n, &m);bk = sqrt(n);for (i = 1; i <= m; i++){scanf("%d%d", &x, &y);h[x] = y;k[x] = (double)y / x;index = x / bk;for (j = index*bk, ma = 0, cnt[index] = 0; j <= index*bk + bk - 1; j++)if (k[j] > ma)q[index][++cnt[index]] = k[j], ma = k[j];ma = 0, ans = 0;for (j = 0; j <= n / bk; j++){ans += cnt[j] - (upper_bound(q[j] + 1, q[j] + 1 + cnt[j], ma) - q[j] - 1);ma = max(ma, q[j][cnt[j]]);}printf("%d\n", ans);}return 0; }

转载于:https://www.cnblogs.com/zfyouxi/p/5390140.html

总结

以上是生活随笔为你收集整理的bzoj-2957 楼房重建的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。