[PAT A1108~A1111]Finding Average、Group Photo、Complete Binary Tree、Online Map_综合

[PAT A1108~A1111]Finding Average、Group Photo、Complete Binary Tree、Online Map

本次题目为连续的四道题，分值为20、25、25、30，可以当做模拟考来练习。

[PAT A1108]Finding Average

题目描述

The basic task is simple: given N real numbers, you are supposed to calculate their average. But what makes it complicated is that some of the input numbers might not be legal. A legal input is a real number in [?1000,1000] and is accurate up to no more than 2 decimal places. When you calculate the average, those illegal numbers must not be counted in.

输入格式

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then N numbers are given in the next line, separated by one space.

输出格式

For each illegal input number, print in a line ERROR: X is not a legal number where X is the input. Then finally print in a line the result: The average of K numbers is Y where K is the number of legal inputs and Y is their average, accurate to 2 decimal places. In case the average cannot be calculated, output Undefined instead of Y. In case K is only 1, output The average of 1 number is Yinstead.

输入样例1

7
5 -3.2 aaa 9999 2.3.4 7.123 2.35

输出样例1

ERROR: aaa is not a legal number
ERROR: 9999 is not a legal number
ERROR: 2.3.4 is not a legal number
ERROR: 7.123 is not a legal number
The average of 3 numbers is 1.38

输入样例2

2
aaa -9999

输出样例2

ERROR: aaa is not a legal number
ERROR: -9999 is not a legal number
The average of 0 numbers is Undefined

解析

1.题目大意：首先给出n和n个数，然后计算它们的平均数，其中只有规范的数字可以被纳入计算（规范的数字指的是，是整数或者浮点数，并且小数位不超过两位，且数字的值得范围在-1000~1000之间）

2.对于字符串的题目，我是很不擅长的，第一次做的时候没有考虑到小数点位数要不超过两位，所以只拿了5分。后面考虑小数点位数之后，也还是只拿到了18分，实在是找不到bug了。这里就不贴出我自己的代码了。

3.这里参考了柳神的代码（侵删），主要要讲的是sscanf和sprintf函数，可以很方便地处理这些问题。一开始对sscanf和sprintf不太了解，于是自己测试了一些数据之后，大体归纳一下：

测试代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
int main() {char a[50];char b[50];while (true){double temp;scanf("%s", a);sscanf(a, "%lf", &temp);sprintf(b, "%.2f", temp);cout << a << " " << temp << " " << b << endl;}return 0;
}

可见，以%lf输入字符串，只会读取从首字符开始的到第一个小数点的数，并且整数位+小数位=6（也就是精度），这里由于合适的数在-1000到1000，意思是整数部分最多占4位，小数部分即使超过2位也不要紧，第一次完成的转换至少能保留两位，所以不用担心精度的问题。在我多次试验之后发现sscanf和sprintf比之于stof函数的区别就是，如果sscanf和sprintf读数出错，那么不会报错，只是相当于没做过，而stof如果不能准确读出数的话，会直接报错导致程序不能运行。

4..这里直接上柳神的代码了，侵删：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
int main() {int n, cnt = 0;char a[50], b[50];double temp, sum = 0.0;cin >> n;for (int i = 0; i < n; i++) {scanf("%s", a);sscanf(a, "%lf", &temp);sprintf(b, "%.2f", temp);int flag = 0;for (int j = 0; j < strlen(a); j++)if (a[j] != b[j]) flag = 1;if (flag || temp < -1000 || temp > 1000) {printf("ERROR: %s is not a legal number\n", a);continue;}else {sum += temp;cnt++;}}if (cnt == 1)printf("The average of 1 number is %.2f", sum);else if (cnt > 1)printf("The average of %d numbers is %.2f", cnt, sum / cnt);elseprintf("The average of 0 numbers is Undefined");return 0;
}

[PAT A1109]Group Photo

题目描述

Formation is very important when taking a group photo. Given the rules of forming K rows with N people as the following:

The number of people in each row must be N/K (round down to the nearest integer), with all the extra people (if any) standing in the last row;
All the people in the rear row must be no shorter than anyone standing in the front rows;
In each row, the tallest one stands at the central position (which is defined to be the position (m/2+1), where m is the total number of people in that row, and the division result must be rounded down to the nearest integer);
In each row, other people must enter the row in non-increasing order of their heights, alternately taking their positions first to the right and then to the left of the tallest one (For example, given five people with their heights 190, 188, 186, 175, and 170, the final formation would be 175, 188, 190, 186, and 170. Here we assume that you are facing the group so your left-hand side is the right-hand side of the one at the central position.);
When there are many people having the same height, they must be ordered in alphabetical (increasing) order of their names, and it is guaranteed that there is no duplication of names.

Now given the information of a group of people, you are supposed to write a program to output their formation.

输入格式

Each input file contains one test case. For each test case, the first line contains two positive integers N (≤10?4??), the total number of people, and K (≤10), the total number of rows. Then N lines follow, each gives the name of a person (no more than 8 English letters without space) and his/her height (an integer in [30, 300]).

输出格式

For each case, print the formation -- that is, print the names of people in K lines. The names must be separated by exactly one space, but there must be no extra space at the end of each line. Note: since you are facing the group, people in the rear rows must be printed above the people in the front rows.

输入样例

10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159

输出样例

Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

解析

1.题目大意：这道题目最烦的地方就在于：长！其实读懂了就还好，这个题目考察的主要是排序，首先输入n,k，n表示人数，k表示行数，即一共要排多少行，并且每行n/k个人，多的人补到最后一行。第i行比第i-1行所有人都要高，且每行里面按照1~m，首先最高的站在m/2+1的位置，然后第二高的人站在当前队列最左边，第三高的人站在当前队列最右边，第四高的人站在当前队列最左边，依次类推。如果有两个人身高相同，那么按名字从低到高排。

2.没什么难度，看明白就好，我使用了一个vector，然后按照身高从高到低排序，相同身高的按照姓名从低到高排序，每次从vector拿出每一行对应的人，按位置排序即可。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10010;
struct node {string name;  //姓名int tall;  //身高
};
bool cmp(node n1, node n2) {  //排序函数if (n1.tall == n2.tall) return n1.name < n2.name;else return n1.tall > n2.tall;
}
int main()
{int n, k;vector<node> people;node r1[maxn], r2[maxn]; //r1用于存放某一行未排序的人，r2存放排好序的人，输出r2即可scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) {node temp;cin >> temp.name >> temp.tall;people.push_back(temp);}sort(people.begin(), people.end(), cmp);for (int i = k; i >= 1; i--) {int num;  //num存放该行的人数if (i == k) num = n - (k - 1)*(n / k); //如果是最后一行else num = n / k;for (int j = 1; j <= num; j++) {  //依次取出排好序的到r1中来r1[j] = people[0];people.erase(people.begin());}int pos = num / 2 + 1, offset = 0; //pos表示中心位置，offset为偏移量for (int j = 1; j <= num; j++) {if (j % 2 == 1) r2[pos + offset] = r1[j];else r2[pos - offset] = r1[j];if (j % 2 == 1) offset++;}for (int j = 1; j <= num; j++) {cout << r2[j].name;if (j != num) printf(" ");}printf("\n");}return 0;
}

[PAT A1110]Complete Binary Tree

题目描述

Given a tree, you are supposed to tell if it is a complete binary tree.

输入格式

Each input file contains one test case. For each case, the first line gives a positive integer N (≤20) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N?1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.

输出格式

For each case, print in one line YES and the index of the last node if the tree is a complete binary tree, or NO and the index of the root if not. There must be exactly one space separating the word and the number.

输入样例1

9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -

输出样例1

YES 8

输入样例2

8
- -
4 5
0 6
- -
2 3
- 7
- -
- -

输出样例2

NO 1

解析

1.题目大意：给出n个结点和他们的子结点编号，判断这是不是一棵完全二叉树。

2.这道题目不算难，就是正常的套路，看到完全二叉树就想到完全二叉树的表示，即数组静态表示。

#include<iostream>
#include<string>
using namespace std;
const int maxn = 30;
struct node {  //结点的结构体int left = -1, right = -1;  
};
int n;
bool notroot[maxn]; //判断某个结点是不是根结点
node Tree[maxn];  //存储树的第一种结构
int BiTree[maxn]; //存储二叉树的结构
void Traverse(int root,int pos);
int main()
{fill(BiTree, BiTree + maxn, -1);scanf("%d", &n);for (int i = 0; i < n; i++) {string s1, s2;cin >> s1 >> s2;if (s1 != "-") {Tree[i].left = stoi(s1);notroot[stoi(s1)] = true; //该结点的左子结点不为根结点}if (s2 != "-") {Tree[i].right = stoi(s2);notroot[stoi(s2)] = true; //该结点的左子结点不为根结点}}int root = -1;for (int i = 0; i < n; i++) {if (notroot[i] == false) {root = i;break;}}Traverse(root, 1);bool ok = true;for (int i = 1; i <= n; i++) {if (BiTree[i] == -1) {ok = false;break;}}if (ok) printf("YES %d", BiTree[n]);else printf("NO %d", root);return 0;
}
void Traverse(int root,int pos) {BiTree[pos] = root;  if (Tree[root].left != -1) Traverse(Tree[root].left, 2 * pos); //左儿子不为空，将它填入2*pos的位置if (Tree[root].right != -1) Traverse(Tree[root].right, 2 * pos + 1); //右儿子不为空，将它填入2*pos+1的位置
}

[PAT A1110]Complete Binary Tree

题目描述

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

输入格式

Each input file contains one test case. For each case, the first line gives two positive integers N (2≤N≤500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:

V1 V2 one-way length time

where V1 and V2 are the indices (from 0 to N?1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.

Finally a pair of source and destination is given.

输出格式

For each case, first print the shortest path from the source to the destination with distance D in the format:

Distance = D: source -> v1 -> ... -> destination

Then in the next line print the fastest path with total time T:

Time = T: source -> w1 -> ... -> destination

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:

Distance = D; Time = T: source -> u1 -> ... -> destination

输入样例1

输出样例1

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5

输入样例2

输出样例2

Distance = 3; Time = 4: 3 -> 2 -> 5

解析

1.这道题目是最短路径问题，不过考察了两个最短路径，所以我写了两个迪杰斯特拉和两个DFS。第一个是要求最短路径，第二标准为如果路径长相等，那么输出用时最少的路径。第二个要求最少时间，第二标准为，如果时间相等，输出结点数最少的路径。

2.总体来说就是套模板，不算难，但是代码量很大，要细心：

#include<iostream>
#include<vector>
using namespace std;
const int maxn = 510;
const int INF = 1000000000;
int Graph[maxn][maxn], Time[maxn][maxn]; //路径长数组，时间数组
int d[maxn]; 
bool visit[maxn];
int n, k, start, dest;
int mindis = INF, mintime = INF, minnode = INF;
vector<int> pre1[maxn], pre2[maxn];
vector<int> tempr, r1, r2;
void Dijkstra1(int s);
void Dijkstra2(int s);
void DFS1(int s);
void DFS2(int s);
int main()
{fill(Graph[0], Graph[0] + maxn * maxn, INF);fill(Time[0], Time[0] + maxn * maxn, INF);scanf("%d%d", &n, &k);for (int i = 0; i < k; i++) {int v1, v2, mod, len, time;scanf("%d%d%d%d%d", &v1, &v2, &mod, &len, &time);if (mod == 1) { //mod==1表示是单向的，mod==0表示的是双向的Graph[v1][v2] = len;Time[v1][v2] = time;}else {Graph[v1][v2] = Graph[v2][v1] = len;Time[v1][v2] = Time[v2][v1] = time;}}scanf("%d%d", &start, &dest);Dijkstra1(start);Dijkstra2(start);DFS1(dest);tempr.clear();  //记得清除temprmintime = INF;DFS2(dest);if (r1 == r2) {cout << "Distance = " << mindis << "; Time = " << mintime<<": ";for (int i = r1.size() - 1; i >= 0; i--) {printf("%d", r1[i]);if (i != 0) printf(" -> ");}}else {cout << "Distance = " << mindis << ": ";for (int i = r1.size() - 1; i >= 0; i--) {printf("%d", r1[i]);if (i != 0) printf(" -> ");}printf("\n");cout << "Time = " << mintime << ": ";for (int i = r2.size() - 1; i >= 0; i--) {printf("%d", r2[i]);if (i != 0) printf(" -> ");}}return 0;
}
void Dijkstra1(int s) {fill(visit, visit + maxn, false);fill(d, d + maxn, INF);d[s] = 0;for (int i = 0; i < n; i++) {int u = -1, min = INF;for (int j = 0; j < n; j++) {if (visit[j] == false && d[j] < min) {u = j;min = d[j];}}if (u == -1) return;visit[u] = true;for (int v = 0; v < n; v++) {if (visit[v] == false && Graph[u][v] != INF) {if (Graph[u][v] + d[u] < d[v]) {d[v] = Graph[u][v] + d[u];pre1[v].clear();pre1[v].push_back(u);}else if (Graph[u][v] + d[u] == d[v]) {pre1[v].push_back(u);}}}}
}
void Dijkstra2(int s) {fill(visit, visit + maxn, false);fill(d, d + maxn, INF);d[s] = 0;for (int i = 0; i < n; i++) {int u = -1, min = INF;for (int j = 0; j < n; j++) {if (visit[j] == false && d[j] < min) {u = j;min = d[j];}}if (u == -1) return;visit[u] = true;for (int v = 0; v < n; v++) {if (visit[v] == false && Time[u][v] != INF) {if (Time[u][v] + d[u] < d[v]) {d[v] = Time[u][v] + d[u];pre2[v].clear();pre2[v].push_back(u);}else if (Time[u][v] + d[u] == d[v]) {pre2[v].push_back(u);}}}}
}
void DFS1(int s) {if (s == start) {int stime = 0, sdis = 0;tempr.push_back(s);for (int i = tempr.size() - 1; i >= 1; i--) {int id1 = tempr[i];int id2 = tempr[i - 1];stime += Time[id1][id2];sdis += Graph[id1][id2];}if (stime < mintime) {r1 = tempr;mindis = sdis;mintime = stime;}tempr.pop_back();return;}tempr.push_back(s);for (int i = 0; i < pre1[s].size(); i++) DFS1(pre1[s][i]);tempr.pop_back();
}
void DFS2(int s) {if (s == start) {int stime = 0;tempr.push_back(s);int snode = tempr.size();for (int i = tempr.size() - 1; i >= 1; i--) {int id1 = tempr[i];int id2 = tempr[i - 1];stime += Time[id1][id2];}if (snode < minnode) {r2 = tempr;minnode = snode;mintime = stime;}tempr.pop_back();return;}tempr.push_back(s);for (int i = 0; i < pre2[s].size(); i++) DFS2(pre2[s][i]);tempr.pop_back();
}