[STL离散化]Skyscrapers的lower_bound系列

总觉得再不整理就会错失一亿个题（不是

首先　　lower_bound(arr,arr+len,x)　　返回第一个不小于x的位置

　　　　upper_bound(arr,arr+len,x)　　第一个大于x的位置

　　　　unique(arr,arr+len)　　全部不同的元素的最后一个的位置，所以我们想知道有多少个不同的元素的时候  n=unique(arr,arr+len)-arr（根据起始下标决定要不要+-1）;啊记得要sort啊╰(*°▽°*)╯

那么离散化的时候，重复元素的值就会相同了（显然我们用unique只记一次）

　　　　CF-#545  C.Skyscrapers

　　　　　　考虑怎么数大小考虑了一个下午，整了三个数组记录大小发现根本搞不过来，为什么我完全想不到lower_bound这种东西呢嘤（因为不会啦!）

　　　　　　总之第几小的话就是lower_bound-arr+1啦

　　　　　　二维数组的lower_bound还是第一次写呢，面白owo

#include
#include
#include
using namespace std;
typedef long long ll;
int n, m;
int a[1005][1005], b[1005][1005], mat[1005][1005];
int mc[1005],mr[1005];int main()
{cin >> n >> m;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {scanf("%d", &a[i][j]);b[j][i] = mat[i][j] = a[i][j];}for (int i = 0; i < n; i++)sort(a[i], a[i] + m), mr[i] = unique(a[i], a[i] + m) - a[i];for (int i = 0; i < m; i++)sort(b[i], b[i] + n), mc[i] = unique(b[i], b[i] + n) - b[i];for (int i = 0; i < n; i++,cout<<endl)for (int j = 0; j < m; j++) {int p = lower_bound(a[i], a[i] + mr[i], mat[i][j]) - a[i];int q = lower_bound(b[j], b[j] + mc[j], mat[i][j]) - b[j];cout << max(p, q) + max(mr[i] - p, mc[j] - q) << " ";}return 0;
}

　　　　　　有几个小细xia节biao要注意：

　　　　　　因为我们用第一维+n/m来排unique，所以用于对列的那个组的两维下标需要交换位置；

　　　　　　因为是枚举行，sort该行的列所以是for(0,n)arr+m，枚举列时同理；

　　　　　　在最后的那个循环里行就是i，列就是j，不要混用。

下一次补一下lb和ub用得最魔鬼的华师校赛F题巩固一下好了。首先，要安然考完高数期中考_(:з」∠)_

转载于:https://www.cnblogs.com/non-/p/10914681.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！