刷题
徐仓仓 Lv3
  2022-08-19 21:45:44 2022-08-19 21:45    

📅time:8.19 -

🍔题目：

1101 25 Quick Sort
1105 25 Spiral Matrix

因子求解

已知N，求a*b=N，且a-b最小。

1
2
3
4
5
6
7
8
int a = sqrt(N);
	int b ;
	for(;a>=1;a--){
		if (N % a == 0) {
			b = N / a;
			break;
		}
	}

附录

1101 25 Quick Sort

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
32
33
34
35
36
37
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
const int INF = 1000000000;
int num[100010];
int mini[100010];
vector<int>ans;
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	int small = INF;
	for (int i = N - 1; i >= 0; i--) {
		mini[i] = small;
		if (small > num[i]) {
			small = num[i];
		}
	}
	int big = -INF;
	for (int i = 0; i < N; i++) {
		if (big < num[i] && num[i] < mini[i])
			ans.push_back(num[i]);
		if (big < num[i]) {
			big = num[i];
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
		printf("%d", ans[i]);
		if (i != ans.size() - 1) printf(" ");
	}
	printf("\n");
}

1105 Spiral Matrix

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
int N;
int num[10010];
bool cmp(int a, int b) {
	return a > b;
}
int main() {
	cin >> N;
	int a = sqrt(N);
	int b ;
	for(;a>=1;a--){
		if (N % a == 0) {
			b = N / a;
			break;
		}
	}
	for (int i = 0; i < N; i++) {
		scanf("%d", &num[i]);
	}
	sort(num, num + N, cmp);
	vector<vector<int> >G(b, vector<int>(a));
	int level = a / 2 + a % 2;
	int t = 0;
	for (int i = 0; i < level; i++) {
		for (int j = i; j <= a - 1 - i && t <= N - 1; j++) {
			G[i][j] = num[t++];
		}
		for (int j = i + 1; j <= b - i - 2 && t <= N - 1; j++) {
			G[j][a - i - 1] = num[t++];
		}
		for (int j = a - i - 1; j >= i && t <= N - 1; j--) {
			G[b - i - 1][j] = num[t++];
		}
		for (int j = b - 2 - i; j > i && t <= N - 1; j--) {
			G[j][i] = num[t++];
		}
	}
	for (int i = 0; i < b; i++) {
		for (int j = 0; j < a; j++) {
			printf("%d", G[i][j]);
			if (j != a - 1) printf(" ");
		}
		printf("\n");
	}
}
 Comments