本文主要是介绍算法训练:pat甲级训练(三道基础题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第一题:1005 Spell It Right (20分)
我的AC代码:算法使用的是映射,难度:简单题
#include <iostream>
#include <string>
#include <stack>
using namespace std;
const int maxn = 105;
int main() {
char* Val = new char[maxn] {'\0'};
string Map[10] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
int res = 0;
cin >> Val;
for (int i = 0; '\0' != Val[i]; ++i)
res += (Val[i] - '0');
stack<string> ans;
if (!res)
cout << Map[0];
else {
while (res) {
ans.push(Map[res % 10]);
res /= 10;
}
while (1 < (int)ans.size()) {
cout << ans.top() << ' ';
ans.pop();
}
cout << ans.top();
}
return 0;
}
第二题:1006 Sign In and Sign Out (25分)
我的AC代码:主要练习STL&引用传参&排序,难度:简单题
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct Student {
string id;
int sHour, sMinu, sSeco;
int tHour, tMinu, tSeco;
Student(string id_, int Hour_, int Minu_, int Seco_, int _Hour, int _Minu, int _Seco) :id(id_), sHour(Hour_), sMinu(Minu_), sSeco(Seco_), tHour(_Hour), tMinu(_Minu), tSeco(_Seco) { }
};
vector<Student> VecStu;
bool cmp1(Student s1, Student s2) {
if (s1.sHour != s2.sHour)
return s1.sHour < s2.sHour;
else if (s1.sMinu != s2.sMinu)
return s1.sMinu < s2.sMinu;
else
return s1.sSeco < s2.sSeco;
}
bool cmp2(Student s1, Student s2) {
if (s1.tHour != s2.tHour)
return s1.tHour > s2.tHour;
else if (s1.tMinu != s2.tMinu)
return s1.tMinu > s2.tMinu;
else
return s1.tSeco > s2.tSeco;
}
int parseInt(string str) {
int num = 0;
for (int i = 0; '\0' != str[i]; ++i)
num = num * 10 + (str[i] - '0');
return num;
}
void getTime(int& H, int& M, int& S, string str) {
H = parseInt(str.substr(0, 2));
M = parseInt(str.substr(3, 2));
S = parseInt(str.substr(6));
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
string id, sTime, tTime;
cin >> id >> sTime >> tTime;
int sHour, sMinu, sSeco;
getTime(sHour, sMinu, sSeco, sTime);
int tHour, tMinu, tSeco;
getTime(tHour, tMinu, tSeco, tTime);
VecStu.push_back(Student(id, sHour, sMinu, sSeco, tHour, tMinu, tSeco));
}
Student TempFirst = VecStu[0], TempLast = VecStu[0];
for (int i = 1; i < n; ++i) {
if (cmp1(VecStu[i], TempFirst))
TempFirst = VecStu[i];
if (cmp2(VecStu[i], TempLast))
TempLast = VecStu[i];
}
cout << TempFirst.id << ' ' << TempLast.id;
return 0;
}
第三题:1007 Maximum Subsequence Sum (25分)
我的AC代码:维护最优子序列,变量模拟下标移动,难度中等题
#include <iostream>
using namespace std;
const int maxn = 10005;
int n, a[maxn], s, t, j, ans = -1, cnt;
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt += a[i];
if (cnt < 0) {
cnt = 0;
j = i + 1;
}
else if (cnt > ans) {
ans = cnt;
s = j;
t = i;
}
}
if (ans >= 0)
cout << ans << ' ' << a[s] << ' ' << a[t];
else
cout << 0 << ' ' << a[0] << ' ' << a[n - 1];
return 0;
}
这篇关于算法训练:pat甲级训练(三道基础题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!