从标准输入读取两个正整数,求这两个数的最大公约数。
输入示例:
35 49
输出示例:
7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return (b == 0 ? a : gcd(b, a % b));
}
int main(int argc, char *argv[]) {
int a, b;
cin >> a >> b;
if (b > a) swap(a, b);
cout << gcd(a, b);
return 0;
}
|
求长度为n的无序数组中第k大的数。数组从文件array.in
中读取,首先给出n和k,然后给出数组的n个元素。
输入示例:
10 7
6 2 20 99 37 100 33 28 78 44
输出示例:
44
本题千万不要先排序完再获取第k个元素,这样估计分得被扣完。该题有两种比较好的思路:
- 基于堆排序,找到第k大的元素即停止排序。
- 基于快速排序,因为快速排序每一趟可以确定一个元素的位置,所以递归时只需要向一个方向递归即可。
下述代码采用基于快速排序的方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
void partition(vector<int> &a, int l, int r, int k) {
if (l >= r) return;
int base = a[l];
int i = l, j = r;
while (i < j) {
while (i < j && a[j] >= base) j--;
a[i] = a[j];
while (i < j && a[i] <= base) i++;
a[j] = a[i];
}
a[i] = base;
if (k == i) return;
else if (i < k) partition(a, i + 1, r, k);
else partition(a, l, i - 1, k);
}
int main(int argc, char *argv[]) {
int n, k;
ifstream ifs("./array.in");
ifs >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) ifs >> a[i];
partition(a, 0, n - 1, k - 1);
cout << a[k - 1];
return 0;
}
|
从文件number.in
中读取若干个正整数,求出它们最大的组合数,输出到标准输出中。
输入示例:
123 456 78 782 789
输出示例:
78978782456123
将正整数当作字符串读入,然后对这些字符串进行排序,依次对字符串的高位数字进行比较,将高位数字较大的字符串排在前面。注意对长度不等的字符串的处理,比如78
和782
,应该组合为78782
而不是78278
。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
bool cmp(const string &l, const string &r) {
int lsize = l.size();
int rsize = r.size();
int maxv = max(l.size(), r.size());
for (int i = 0; i < maxv; i++) {
if (l[i % lsize] == r[i % rsize])
continue;
return l[i % lsize] > r[i % rsize];
}
return true;
};
int main(int argc, char *argv[]) {
ifstream ifs("./number.in");
vector<string> v;
string s;
while (ifs >> s)
v.push_back(s);
sort(v.begin(), v.end(), cmp);
for (const auto &s : v) cout << s;
return 0;
}
|