• 欢迎光临~

YACS 两数之积 题解

0 的数量为 \$cnt0\$ 个。

----------------------------------

\$\$x1=cnt1*(cnt1-1)/2+cnt2*(cnt2-1)/2\$\$

\$\$x0=cnt0*(n-1)\$\$

\$\$x2=cnt1*cnt2\$\$

-----------------------------------

1. 若 \$t≤x1\$ ，则这个第 \$t\$ 大数一定是在 \$b\$ 序列中所有的正数中产生的,

2. 若 \$x1<t≤x1+x0\$，则这个第 \$t\$ 大数就是 0 。

3. 若 \$t>x1+x0\$  则这个第 \$t\$ 大数一定是在 \$x2\$ 个负数中产生的，

```#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 1e7+10;

ll bz[maxn]= {0}, bf[maxn]= {0};
ll x=0, n=0, t=0;
ll cnt1=0, cnt0=0, cnt2=0;
ll x1=0, x0=0, x2=0;
ll l=0 , r=0;

char _buf[1<<21],*p1=_buf,*p2=_buf;
char ch;bool ff;
template <typename T>
x=0;ff=false;ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')ff=true;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
if(ff)x=~x+1;
return;
}
template <typename T>
inline void write(T x){
if(x<0)putchar('-'),x=~x+1;
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
do{c=getchar();}while(ch<'0'||ch>'9');return;
}
template <typename T>
inline void writeln(T x){write(x);putchar('n');return;}
}

bool judge(ll num) {
ll tmp = 0;
for (int i = 0; i < cnt1; i++) {
ll p = upper_bound(bz, bz+cnt1, num/bz[i])-bz;
if (p > i) tmp += cnt1-p;
else tmp += cnt1-i-1;
}
for (int i = 0; i < cnt2; i++) {
ll p = upper_bound(bf, bf+cnt2, num/bf[i])-bf;
if (p > i) tmp += cnt2-p;
else tmp += cnt2-i-1;
}
return tmp >= t;
}

bool check(ll num) {
ll tmp = 0;
for (int i = 0; i < cnt1; i++) {
tmp += cnt2-(upper_bound(bf,bf+cnt2, floor((double)num/bz[i]))-bf);
}
return tmp >= t-(x1+x0);
}

int main() {
for (int i = 0; i < n; i++) {
if (x > 0) bz[cnt1++] = x;
else if (x == 0) cnt0 ++;
else bf[cnt2++] = x;
}
x1 = cnt1*(cnt1-1)/2+cnt2*(cnt2-1)/2;
x0 = cnt0*(n-1);x2 = cnt1*cnt2;
if (t <= x1) {
for(int i=0; i<cnt2; i++)bf[i]*=-1;
sort(bz,bz+cnt1);
sort(bf,bf+cnt2);
l = min(bz[0]*bz[1], bf[0]*bf[1]);
r = max(bz[cnt1-1]*bz[cnt1-2], bf[cnt2-1]*bf[cnt2-2]);
while (l <= r) {
ll mid = (l+r)>>1;
if (judge(mid))l = mid+1;
else r = mid-1;
}
writeln(l);
}
else if (t > x1 && t <= x1+x0)putchar('0');
else {
sort(bz, bz+cnt1);
sort(bf, bf+cnt2);
l = bz[0]*bf[0];
r = bz[cnt1-1]*bf[cnt2-1];
while (l <= r) {
ll mid = (l+r)/2;
if (check(mid))l = mid+1;
else r = mid-1;
}
writeln(l);
}
return 0;
}```
View Code