Java教程

基础算法训练:还是pat乙级(25分题已经全部刷完!AK!)

本文主要是介绍基础算法训练:还是pat乙级(25分题已经全部刷完!AK!),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第一题:1070 结绳 (25分)

在这里插入图片描述

我的AC代码:这题小顶堆不解析哈

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

priority_queue<double, vector<double>, greater<double> > q;
int main() {
	int n;
	cin >> n;
	while (n--) {
		double a;
		cin >> a;
		q.push(a);
	}
	while (1 < (int)q.size()) {
		double f = q.top(); q.pop();
		double s = q.top(); q.pop();
		double Next = f / 2.0 + s / 2.0;
		q.push(Next);
	}
	cout << floor(q.top());
	return 0;
}
第二题:1065 单身狗 (25分)

在这里插入图片描述

我的AC代码:注意没有落单客人的情况,*(ans.begin() - 1)会非法访问!也就是第二个测试点"段错误"的缘故

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 10005;
map<int, int> mp;
int n, m, a[maxn], b[maxn];
vector<int> ans;
int main() {
	scanf("%d", &n);
	while (n--) {
		int a, b;
		scanf("%d %d", &a, &b);
		mp[a] = b;
		mp[b] = a;
	}
	scanf("%d", &m);
	fill(a, a + m, -1);
	fill(b, b + m, -1);
	for (int i = 0; i < m; ++i) {
		scanf("%d", &a[i]);
		b[i] = a[i];
	}
	sort(b, b + m);
	for (int i = 0; i < m; ++i) {
		if (mp.find(a[i]) == mp.end())
			ans.push_back(a[i]);
		else if (!binary_search(b, b + m, mp[a[i]]))
			ans.push_back(a[i]);
	}
	printf("%d\n", (int)ans.size());
	if ((int)ans.size() > 0) {
		sort(ans.begin(), ans.end());
		for (vector<int>::iterator it = ans.begin(); ans.end() - 1 != it; ++it)
			printf("%05d ", *it);
		printf("%05d", ans[(int)ans.size() - 1]);
	}
	return 0;
}
第三题:1050 螺旋矩阵 (25分)

在这里插入图片描述

我的AC代码:我猜你一定记得,曾经c++期末考试的签到题,当时我很惭愧,甚至是羞愧,甚至是痛恨自己,没有签上到

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool cmp(int a, int b) { return a > b; }
int main() {
	int n, a, r, c;
	vector<int> Vec;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a);
		Vec.push_back(a);
	}
	for (int i = (int)sqrt(n); i >= 1; --i) 
		if (!(n % i)) 
		{
			c = i, r = n / i;
			break;
		}
	sort(Vec.begin(), Vec.end(), cmp);
	int** ans = new int* [r];
	for (int i = 0; i < r; ++i)
		ans[i] = new int[c];
	int i = 0, j = 0, Row1 = 0, Row2 = r - 1, Col1 = 0, Col2 = c - 1;
	while (i < n) {
		if (!(j & 1)) {
			if (0 == j % 2 && 0 == j % 4) {
				for (int p = Col1; p <= Col2; ++p, ++i)
					ans[Row1][p] = Vec[i];
				j++;
				Row1++;
			}
			else {
				for (int p = Col2; p >= Col1; --p, ++i)
					ans[Row2][p] = Vec[i];
				j++;
				Row2--;
			}
		}
		else {
			if (1 == j % 2 && 1 == j % 4) {
				for (int p = Row1; p <= Row2; ++p, ++i)
					ans[p][Col2] = Vec[i];
				Col2--;
				j++;
			}
			else {
				for (int p = Row2; p >= Row1; --p, ++i)
					ans[p][Col1] = Vec[i];
				Col1++;
				j++;
			}
		}
	}
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			if (j < c - 1)
				printf("%d ", ans[i][j]);
			else
				printf("%d", ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}
第四题:1045 快速排序 (25分)

在这里插入图片描述

我的AC代码:这题我大概讲一下思路:

一开始我想的太简单了,用另一个数组 b[] copy原数组 a[],然后对数组 b[]排序,如果某元素在有序状态下的位次和在原数组中的位次相同,说明原数组的该元素是已经就位的元素。 后来我构造了一个测试用例:
5
5 4 3 2 1

讲道理,应该输出 0,结果却输出了:
1
3
原因是:
排序后数组:1 2 3 4 5
原状态数组:5 4 3 2 1
大家可以看到,这个3貌似就位了,但是其实不应该就位的,这种反向有序的状态,就会导致我们的程序出错!如何解决这个问题呢?一开始还是很烧脑的,后来也是看了柳茹大神的博客,才意识到少考虑了一个点!在顺序的情况下,第 i 个元素一定是前 i 个元素中最大的那个元素! 如果是逆序,则是最小的那个元素,这样就把顺序和逆序区分开来!注意,并不是只有全部元素完全逆序才会出这个bug!只要某连续区间完全逆序,就会出这种bug!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 1e5 + 5;
int n, a[maxn], b[maxn], preMax[maxn];
vector<int> ans;
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		b[i] = a[i];
	}
	preMax[1] = a[1];
	for (int i = 2; i <= n; ++i) {
		if (a[i] > preMax[i - 1])
			preMax[i] = a[i];
		else
			preMax[i] = preMax[i - 1];
	}
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; ++i)
		if (b[i] == a[i] && preMax[i] == a[i])
			ans.push_back(a[i]);
	cout << ans.size() << endl;
	if ((int)ans.size() > 0) {
		for (int i = 0; i < (int)ans.size() - 1; ++i)
			cout << ans[i] << ' ';
		cout << ans[(int)ans.size() - 1];
	}
	cout << endl;
	return 0;
}
这篇关于基础算法训练:还是pat乙级(25分题已经全部刷完!AK!)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!