are you ok?

题目描述
一个长度为n的数组a,数组下标从0开始。现在要求你查询从左到右第一个不小于k的数字a[i], 输出i,并且马上把a[i-1]++;如果你找到的a[i]中的i等于0,那么a[0-1]是非法的,因此只要输出i就行了,不进行a[i-1]++;如果你在数组中找不到一个数字不小于k,则输出”are you ok ”

输入描述:
多组输入,输入直到遇到EOF为止;

第一行输入两个整数n和q,表示数组a中有n个整数,q表示q次查询;

第二行输入n个整数;

第三行到后2+q行,每行输入一个数字k,表示要求你查询从左到右第一个不小于k的数字并马上输出。

注意:1 < n, q <= 1e6, a[i]和k是一个int型的整数
输出描述:
见输入。
示例1

输入
复制

3 4
1 2 8
2
2
8
9

输出
复制

1
0
2
are you ok


本来以为要写一个线段树套主席树,突然一想,其实我们维护最大值即可。为什么呢,我们每次考虑大区间的最大值,如果最大值大于等于k,那么这个区间肯定存在一个合法的值,然后我们递归考虑左区间,如果左区间的最大值大于等于k,那么我们递归考虑左区间,不然递归考虑右区间。而且因为我们优先考虑左区间,所以找到的必然是最左边的值。


AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
int n,q,a[N];
struct node{
	int l,r,max;
}t[N<<2];
inline void push_up(int p){
	t[p].max=max(t[p<<1].max,t[p<<1|1].max);
}
void build(int p,int l,int r){
	t[p].l=l;	t[p].r=r;	
	if(l==r){
		t[p].max=a[l];	return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
	push_up(p);
}
void change(int p,int x){
	if(t[p].l==t[p].r){
		t[p].max++;	return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	change(p<<1,x);
	else	change(p<<1|1,x);
	push_up(p);
}
int ask(int p,int x){
	if(t[p].l==t[p].r){
		return t[p].l;
	}
	int mid=t[p].l+t[p].r>>1;
	if(t[p<<1].max>=x)	return ask(p<<1,x);
	else	return ask(p<<1|1,x);
}
signed main(){
	while(~scanf("%d %d",&n,&q)){
		for(int i=1;i<=n;i++)	scanf("%d",&a[i]);	build(1,1,n);	
		while(q--){
			int x;	scanf("%d",&x);
			if(t[1].max<x){
				puts("are you ok");	continue;
			}
			int id=ask(1,x);	printf("%d\n",id-1);
			if(id!=1)	change(1,id-1);
		}
	}
	return 0;
}
全部评论

相关推荐

10-09 00:50
已编辑
长江大学 算法工程师
不期而遇的夏天:1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务