洛谷 AT2561 题解

洛谷题目传送门 | AT 原题传送门

思路

桶的思想。

用数组 $t$ 存储 $a$ 出现的次数，然后循环，用 $k$ 减每个数出现的次数，看在哪个数时满足 $k \leq 0$ 的条件，直接输出这个数的下标即可。

注意不开 $\texttt{long long}$ 见祖宗

代码

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll n,k,a,b;
ll t[100010],ans=0;
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&a,&b);
		t[a]+=b;//t为桶，增加a的个数
	}
	while(k>0)//当k<=0时跳出循环
	{
		k-=t[++ans];//每次k自减t[++ans]
	}
	printf("%lld\n",ans);
	return 0;
}