Question

一道ACM编程题 怎么做法？

题目地址：http://acm.tju.edu.cn/toj/showp3495.html
大概意思是：
读入N个数 和一个数T
2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率。

我的想法是二分 不知道正不正确

Answer 1

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