[徐州网络赛][单调栈+二分]E- XKC’s basketball team

发布于 2019-09-24  208 次阅读


https://nanti.jisuanke.com/t/41387

题目大意:从左到右1-n个数字 每个数字都有自己的权值 寻找出每个数字右边比自己至少大m的数字之间的距离

思路:见AC代码

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
const int maxn = 5e5 + 5;

int n, m;
int arr[maxn];//存数
int ans[maxn];
int cnt = 0;
int st[maxn];
int v[maxn];

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	st[++cnt] = arr[n];//最后一个元素入栈
	ans[n] = -1;
	v[cnt] = n;//栈内唯一元素对应的下标
	for (int i = n - 1; i >= 1; --i) {
		int id = lower_bound(st + 1, st + cnt + 1, arr[i] + m) - st;//二分找第一个比自己大m的数字 因为保证栈单调递减 所有搜到的第一个即是最符合题意的一个
		if (id == cnt + 1) {//如果二分的答案等于它自己
			ans[i] = -1;//答案等于-1
		}
		else {
			ans[i] = v[id] - i - 1;//否则答案等于搜到的坐标
		}
		if (st[cnt] < arr[i]) {//如果当前元素大于栈顶元素 就入栈
			st[++cnt] = arr[i];
			v[cnt] = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i];
		if (i != n) cout << " ";
	}
	cout << endl;
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。