@[scp_05_tqr](/space/show?uid=117842) 而且也有一点不一样,还有t组询问
by 开始新的记忆 @ 2019-03-15 20:33:16
可以用一个堆
by wkywkywky @ 2019-03-15 20:33:55
@[开始新的记忆](/space/show?uid=132290) T组询问……加几行代码就行了……没有本质区别
先把做法搞懂吧
by 无意识躺枪人 @ 2019-03-15 20:34:31
你们都在说什么,表示听不懂
by 开始新的记忆 @ 2019-03-15 20:34:41
@[scp_05_tqr](/space/show?uid=117842) 所以我也想搞懂啊
by 开始新的记忆 @ 2019-03-15 20:35:17
@[开始新的记忆](/space/show?uid=132290)
```c
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 5e4+5;
LL a[MAXN], b[MAXN];
LL l,r;
LL Judge(LL x, int n)
{
LL sum = 0, tp;
for(int i=n-1; i>=0; i--)
{
if(x % a[i])
tp = x/a[i]+1;
else
tp = x/a[i];
int tmp = lower_bound(b,b+n,tp)-b;
sum += n-tmp;
if(sum == 0)
break;
}
return sum;
}
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
{
for(int i=0; i<n; i++)
scanf("%lld%lld",&a[i],&b[i]);
sort(a, a+n);
sort(b, b+n);
l = a[0]*b[0], r = a[n-1]*b[n-1];
while(l <= r)
{
LL mid = (l+r)>>1;
LL tmp = Judge(mid, n);
if(tmp < k)
r = mid-1;
else
l = mid+1;
}
printf("%lld\n",l-1);
}
return 0;
}
```
看不懂就去问你教练
by 无意识躺枪人 @ 2019-03-15 20:36:53
@[scp_05_tqr](/space/show?uid=117842) 谢谢,唤起了我一星期前的二分记忆……
by 开始新的记忆 @ 2019-03-15 20:38:26
@[scp_05_tqr](/space/show?uid=117842) lower_bound(b,b+n,tp)是什么意思?
by 开始新的记忆 @ 2019-03-15 20:41:18
@[开始新的记忆](/space/show?uid=132290)
lower_bound(起始地址,结束地址,要查找的数值) 返回的是数值 第一个 出现的位置。
在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置
by 无意识躺枪人 @ 2019-03-15 20:43:36
@[scp_05_tqr](/space/show?uid=117842) 谢谢
by 开始新的记忆 @ 2019-03-15 20:44:13