给出n,m,k,输出在n*m的乘法表中第k小的数。用C++程序写
时间: 2023-06-19 07:05:37 浏览: 95
以下是C++程序实现:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int count(int n, int m, int num) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += min(m, num / i);
}
return cnt;
}
int main() {
int n, m, k;
cin >> n >> m >> k;
int left = 1, right = n * m;
while (left < right) {
int mid = (left + right) / 2;
if (count(n, m, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
cout << left << endl;
return 0;
}
```
首先,我们使用二分查找寻找第k小的数,将查找范围设为区间[1, n\*m],因为乘法表中最小的数是1,最大的数是n\*m。在每次二分查找时,我们通过count函数计算出小于等于mid的数有多少个,如果数量小于k,则第k小的数一定在[mid+1, right]区间内,否则在[left, mid]区间内。
接下来,我们实现count函数来计算小于等于num的数的数量。我们遍历乘法表的每一行,计算出小于等于当前行号i的数有多少个,用min(m, num/i)来限制列数不超过m,因为列数可能小于m。最后将所有行小于等于num的数的数量累加起来。
最终,输出left即为第k小的数。