洛谷题目传送门 | AT 原题传送门
思路
桶的思想。
用数组 tt 存储 aa 出现的次数，然后循环，用 kk 减每个数出现的次数，看在哪个数时满足 k≤0k \leq 0 的条件，直接输出这个数的下标即可。
注意不开 long long\texttt{long long} 见祖宗
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #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;
}
|
