洛谷 AT2561 题解

2022年2月7日 17:56

思路

桶的思想。

用数组 $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;
}

洛谷 AT2561 题解

2022年2月7日 17:56

洛谷题目传送门 | 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;
}

洛谷 AT2561 题解

2022年2月7日 17:56

洛谷题目传送门 | 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;
}