ABC440D题

🥥

2026-01-10 21:44:33

发布于：上海

32阅读

0回复

0点赞

ABC440D题10分钟敲出的乱搞做法一个TLE，其余全AC

#include<bits/stdc++.h>
using namespace std;
long long n,q,a[300005];
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=q;i++)
	{
		long long x,y;
		cin>>x>>y;
		long long p1=lower_bound(a+1,a+n+1,x)-a-1,p2=upper_bound(a+1,a+n+1,x+y-1)-a-1;
		while(p1!=p2)
		{
			y+=p2-p1;
			p1=p2;
			p2=upper_bound(a+1,a+n+1,x+y-1)-a-1;
		}
		cout<<x+y-1<<endl;
	}
	return 0;
}

求正解

有帮助，赞一个

去预览

0/2000

全部评论 1

cjdst

你这个已经十分接近正解了。

注意到答案满足单调性（越大的数排名越高），考虑二分答案。

对于一个数 $k$ ，我们只需要求出 $A$ 中在区间 $[x,k]$ 内的数的数量 $m$ ，则它的排名为 $k-x-m+1$ 。

namespace cjdst{
    void solve(){
		ll n, m;
		std::cin >> n >> m;
		std::vector <ll> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		std::sort(a.begin() + 1, a.begin() + n + 1);
		while(m--){
			int x, y;
			std::cin >> x >> y;
			ll l = x, r = 3e9;
			while(l <= r){
				ll mid = (l + r) >> 1;
				ll idx = (upper_bound(a.begin() + 1, a.begin() + n + 1, mid) - a.begin()) - (lower_bound(a.begin() + 1, a.begin() + n + 1, x) - a.begin());
				if(mid - idx - x + 1 < y) l = mid + 1;
				else r = mid - 1;
			}
			std::cout << l << '\n';
		}
	}
}

时间复杂度 $O(q\log n\log V)$ 。

2026-01-10 来自广东

全部评论 1

热门讨论