返回信息流有两个长度是5000的数组，已经排序好，数据分布大概是这样的：
基本上是数据的范围在[0.5, 3.5]之间，现在将两个序列的每个元素分别相乘，生成一个矩阵，然后用一种方法选500个index，要求这500个index要尽可能的和最大的前500个index重合。
做实验的时候遇到的问题，已经想了很长时间了，也没有一个有效的办法[ema1]
跪求大神指导[ema11]
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #94526同步于 2017/11/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
两个已排序好的序列分别相乘，然后排序
bdyzhy9527
2017/11/28镜像同步13 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
楼上肯定是不行的，n=5000*5000，计算量太大。
首先，把两个数组从小到大排列（纯粹因为习惯），我直观的感觉是首先array1[i<(5000-23) ×array2[j<(5000-23)]这部分数据首先可以排除掉，剩下23*5000*2-23*23大概20万数据，要利用数据线性（或者近似线性）的部分再把一部分数据pass掉。
如果再想想，array1和array2成线性的话，array1 ×array2就会形成一个离散的双曲抛物面zij（xi，yj）=xiyj。怎样求一个离散的马鞍面最大的k个zij？
i、j最后组成的集合将是被ij=C（k）这条双曲线围住的部分。使C'（k）=C*array1[5000-23]*array2[5000-23],（C为常数），把这个曲线外的i，k排除掉。
这还没完，因为还有两个非线性部分相乘的区域同样被排除了，而这两个部分有可能存在top500的元素。想想就很复杂，生成5000*5000矩阵按行列在三维画图的话应该是一个边缘畸变的离散双曲抛物面，在这样一个畸变的曲面求topk，学渣的我感觉数学已经完全不够用了。
如果精确度可以放宽，可以考虑采样，将两个数组采样成为500*500=250000，求top500，先排除（500-23）*（500-23）个数据，剩余23*500*2-23*23大概2万数据，做堆排或者部分快排，得到500点，每个点增加周围八个点，共计4500点，再取500点再排，重复直到500个点收敛。简单粗暴，效果看运气，速度靠人品。
我猜想最后ij集合应该是一个边界处发生畸变的双曲线围成的图形。
从你的数据来看，中间部分基本是线性的，只是前后有畸变，这个问题有点像通信信号里面在边界处产生的噪声，而要求信号里topK个主分量，或许看看信号处理的书也许有好的解决思路。
哇，十分感谢，今天没怎么看论坛回复晚了，我认真看看[ema11]
【 在 unimit 的大作中提到: 】
: 如果精确度可以放宽，可以考虑采样，将两个数组采样成为500*500=250000，求top500，先排除（500-23）*（500-23）个数据，剩余23*500*2-23*23大概2万数据，做堆排或者部分快排，得到500点，每个点增加周围八个点，共计4500点，再取500点再排，重复直到500个点收敛。简单粗暴，效果看运气，速度靠人品。
: 我猜想最后ij集合应该是一个边界处发生畸变的双曲线围成的图形。
: 从你的数据来看，中间部分基本是线性的，只是前后有畸变，这个问题有点像通信信号里面在边界处产生的噪声，而要求信号里topK个主分量，或许看看信号处理的书也许有好的解决思路。
不客气。这个问题很有意思，有没有结果都可以继续讨论。
【 在 bdyzhy9527 的大作中提到: 】
: 哇，十分感谢，今天没怎么看论坛回复晚了，我认真看看
不想打字.. 贴段代码吧, 楼主要是看完还有兴趣可以ping我
vector<int> bigest_n(vector<int> a, vector<int> b, int cnt) {
int l = a[0] * b[0];
int u = a.back() * b.back() + 1;
while (l + 1 != u) {
int m = (l + u) / 2;
int not_less_than_m = 0;
for (int ai = 0, bi = b.size() - 1; ai < a.size(); ai++) {
while (bi >= 0 && a[ai] * b[bi] >= m) {
bi--;
}
not_less_than_m += b.size() - 1 - bi;
}
if (not_less_than_m >= cnt) {
l = m;
} else {
u = m;
}
}
vector<int> ans;
for (int i = 0; i < a.size(); i++) {
for (int j = b.size() - 1; j >= 0; j--) {
if (a[i] * b[j] > l) {
ans.push_back(a[i] * b[j]);
}
}
}
while (ans.size() < cnt) ans.push_back(l);
sort(ans.begin(), ans.end());
return ans;
}
m和n指的是？
【 在 moyuji 的大作中提到: 】
: 相乘取对数就是加法，两个log数组merge sort然后从右端不端添加，直到取到的数子个数m*n >500
你好，为什么要加1，能不能简单描述一下算法
【 在 hiyot 的大作中提到: 】
: 不想打字.. 贴段代码吧, 楼主要是看完还有兴趣可以ping我
: [code=c]
: vector<int> bigest_n(vector<int> a, vector<int> b, int cnt) {
: ...................