一道ACM编程题 大概意思是：读入N个数 和一个数T2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.我的想法是二分

一道ACM编程题 大概意思是：读入N个数 和一个数T2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.我的想法是二分
一道ACM编程题
大概意思是：
读入N个数 和一个数T
2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.
我的想法是二分

一道ACM编程题 大概意思是：读入N个数 和一个数T2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.我的想法是二分
按照最常规的算法,遍历是难以避免的,而我们的算法则希望尽可能的排除掉一些数以减少遍历的量,所以第一步我认为应该先进行无意义数据的排除,至于排除的方法,我的想法是先排序,然后取这一堆数字中最大的数,然后从最小的数开始与这个最大的数求积,如果积小于T,则这个数就不参与遍历,直到找到乘积大于T的第k小的数,则对剩余数据进行遍历,时间复杂度是N-k的N-k次方,也是比较可观的.
第二步,我们可以采用一些方法减少遍历的时间复杂度,我们可以取T的平方根,对经过第一步的数据进行分组,大于平方根的那组数据互相之间乘积必然大于T,小于平方根的那组数据互相之间乘积必然小于T,那么完全遍历的规模就缩小到了组与组之间进行笛卡尔运算的规模,即a个数据和b个数据两两相乘,时间复杂度是a*b,（a+b=N）,此时时间复杂度已经比较可以接受了.
如果数据量特别大,我们也许会需要进行第三步,对于a和b两组数,取a中最大和和b中最小的进行相乘,然后取a中次大的和b中最小的进行相乘.依此类推,继续对数据进行排除.
我描述的应该比较清晰了,acm,当年我手机震动睡过头了,失之交臂啊,祝你成功,而且特别提醒你手机要保持铃声状态.