hdvsyu's blog

Given some segments of rope, you are supposed to chain them into one rope. Each time you may only fold two segments into loops and chain them into one piece, as shown by the figure. The resulting chain will be treated as another segment of rope and can be folded again. After each chaining, the lengths of the original two segments will be halved.

Your job is to make the longest possible rope out of N given segments.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (2 <= N <= 104). Then N positive integer lengths of the segments are given in the next line, separated by spaces. All the integers are no more than 104.

Output Specification:

For each case, print in a line the length of the longest possible rope that can be made by the given segments. The result must be rounded to the nearest integer that is no greater than the maximum length.

Sample Input:

8
10 15 12 3 4 13 1 15

Sample Output:

14

用贪心的思想来解，最长的绳子折叠的次数越少越好。这里用到了优先队列priority_queue，它保证每次插入到队列中的值都是按顺序排列的，因此我们可以尽可能的找到最短的两条线段，折成新的绳子，然后继续找两个最短的绳子做折叠，直到只剩下一条绳子。

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

#include <queue>
#include <cstdio>
#include <functional>
#include <vector>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < n; i++) {
        int temp = 0;
        scanf("%d", &temp);
        q.push(temp);
    }

    while (q.size() > 1) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();

        q.push((a + b) / 2);
    }
    printf("%d", q.top());
}

John got a full mark on PAT. He was so happy that he decided to hold a raffle（抽奖） for his followers on Weibo – that is, he would select winners from every N followers who forwarded his post, and give away gifts. Now you are supposed to help him generate the list of winners.

Input Specification:

Each input file contains one test case. For each case, the first line gives three positive integers M (<= 1000), N and S, being the total number of forwards, the skip number of winners, and the index of the first winner (the indices start from 1). Then M lines follow, each gives the nickname (a nonempty string of no more than 20 characters, with no white space or return) of a follower who has forwarded John’s post. Note: it is possible that someone would forward more than once, but no one can win more than once. Hence if the current candidate of a winner has won before, we must skip him/her and consider the next one.

Output Specification:

For each case, print the list of winners in the same order as in the input, each nickname occupies a line. If there is no winner yet, print “Keep going…” instead.

Sample Input 1:

9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain

Sample Output 1:

PickMe
Imgonnawin!
TryAgainAgain

Sample Input 2:

2 3 5
Imgonnawin!
PickMe

Sample Output 2:

Keep going…

用map来记录一个用户是否已经获过奖了。当s > m，不满足抽奖规则，输出Keep going…；s <= m时，先输出第一个中奖的人，后面中奖的人根据根据规则继续往下推。

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

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

int main() {
    int m = 0, n = 0, s = 0;
    cin >> m >> n >> s;
    vector<string> forward(m + 1);
    for (int i = 1; i <= m; i++) {
        string nickname;
        cin >> nickname;
        forward[i] = nickname;
    }

    if (s > m) {
        cout << "Keep going..." << endl;
    } else {
        map<string, bool> winner;
        cout << forward[s] << endl;
        winner[forward[s]] = true;
        int i = s;
        while (i < m) {
            int cnt = 0;
            while (i < m && cnt < n) {
                i++;
                if (!winner[forward[i]]) {
                    cnt++;
                }
            }
            if (n == cnt) {
                cout << forward[i] << endl;
                winner[forward[i]] = true;
            }
        }
    }
    return 0;
}

问题描述

　　某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

　　一行，为导弹依次飞来的高度

输出格式

　　两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6 2

【分析】第一个问题，最多能拦截的导弹数和最长不下降子序列是相似的。第二个问题，最少要配备的系统数需要用贪心算法来求解；对于最多能拦截的导弹数这个问题，每一枚飞来的导弹被系统拦截，那这一枚导弹后面比当前飞来的导弹高度低的导弹也可以被这套系统拦截，用一个dp数组来保存一套系统最多可以拦截多少导弹数；对于第二个问题，后面飞来的每一枚导弹，都用前面与它高度差最小的那套系统去拦截。

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
50
51
52
53
54
55
56
57

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] missile = reader.readLine().split(" ");
        reader.close();
        int[] high = new int[missile.length];
        for (int i = 0; i < high.length; i++) {
            high[i] = Integer.parseInt(missile[i]);
        }
        System.out.println(getMaxIntercept(high));
        System.out.println(getNumberOfIntercepter(high));
    }

    private static int getMaxIntercept(int[] high) {
        int[] dp = new int[high.length];
        int max = 0;
        for (int i = 0; i < high.length; i++) {
            for (int j = i + 1; j < high.length; j++) {
                if (high[j] <= high[i]) {
                    dp[j] = Integer.max(dp[j], dp[i] + 1);
                    max = Integer.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }

    private static int getNumberOfIntercepter(int[] high) {
        int numberOfIntercepter = 0;
        boolean[] isIntercept = new boolean[high.length];
        for (int i = 0; i < high.length; i++) {
            int midHighDifference = getMinHighDifference(high, i, isIntercept);
            if (midHighDifference == -1) {
                numberOfIntercepter++;
            } else {
                isIntercept[midHighDifference] = true;
            }
        }
        return numberOfIntercepter;
    }

    private static int getMinHighDifference(int[] high, int pos, boolean[] isIntercept) {
        int minHighDifferenceIndex = -1;
        for (int i = 0; i < pos; i++) {
            if (!isIntercept[i] && high[i] >= high[pos]) {
                if (minHighDifferenceIndex == -1 || high[i] < high[minHighDifferenceIndex]) {
                    minHighDifferenceIndex = i;
                }
            }
        }
        return minHighDifferenceIndex;
    }
}

如果你想一个请求，这个请求的返回值是泛型的，你可以会执行下面这么一行代码

1

HashMap<String, String> result = restTemplate.getForObject("url", HashMap.class, ...)

现在，Spring有更好的处理方法

1
2

HashMap<String, String> result = restTemplate.exchange("url", HttpMethod.GET, null, new ParameterizedTypeReference<HashMap<String, String>>() {},
...).getBody();

在RestOperations里面有三个可以接收泛型返回值的exchange方法，如下：

1
2
3
4
5

<T> ResponseEntity<T> exchange(String var1, HttpMethod var2, HttpEntity<?> var3, ParameterizedTypeReference<T> var4, Object... var5) throws RestClientException;

<T> ResponseEntity<T> exchange(String var1, HttpMethod var2, HttpEntity<?> var3, ParameterizedTypeReference<T> var4, Map<String, ?> var5) throws RestClientException;

<T> ResponseEntity<T> exchange(URI var1, HttpMethod var2, HttpEntity<?> var3, ParameterizedTypeReference<T> var4) throws RestClientException;

这里ParameterizedTypeReferences<T>的T就是你要的泛型，像上面的代码一样改掉即可。

参考： [1] https://jira.spring.io/browse/SPR-7023

For a student taking the online course “Data Structures” on China University MOOC (http://www.icourse163.org/), to be qualified for a certificate, he/she must first obtain no less than 200 points from the online programming assignments, and then receive a final grade no less than 60 out of 100. The final grade is calculated by G = (Gmid-termx 40% + Gfinalx 60%) if Gmid-term > Gfinal, or Gfinal will be taken as the final grade G. Here Gmid-term and Gfinal are the student’s scores of the mid-term and the final exams, respectively. The problem is that different exams have different grading sheets. Your job is to write a program to merge all the grading sheets into one.

Input Specification:

Each input file contains one test case. For each case, the first line gives three positive integers: P , the number of students having done the online programming assignments; M, the number of students on the mid-term list; and N, the number of students on the final exam list. All the numbers are no more than 10,000. Then three blocks follow. The first block contains P online programming scores Gp’s; the second one contains M mid-term scores Gmid-term’s; and the last one contains N final exam scores Gfinal’s. Each score occupies a line with the format: StudentID Score, where StudentID is a string of no more than 20 English letters and digits, and Score is a nonnegative integer (the maximum score of the online programming is 900, and that of the mid-term and final exams is 100).

Output Specification:

For each case, print the list of students who are qualified for certificates. Each student occupies a line with the format: StudentID Gp Gmid-term Gfinal G If some score does not exist, output “-1” instead. The output must be sorted in descending order of their final grades (G must be rounded up to an integer). If there is a tie, output in ascending order of their StudentID’s. It is guaranteed that the StudentID’s are all distinct, and there is at least one qualified student.

Sample Input:

6 6 7
01234 880
a1903 199
ydjh2 200
wehu8 300
dx86w 220
missing 400
ydhfu77 99
wehu8 55
ydjh2 98
dx86w 88
a1903 86
01234 39
ydhfu77 88
a1903 66
01234 58
wehu8 84
ydjh2 82
missing 99
dx86w 81

Sample Output:

missing 400 -1 99 99
ydjh2 200 98 82 88
dx86w 220 88 81 84
wehu8 300 55 84 84

解析见乙级：https://www.hdvsyu.com/posts/1413/

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
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <cstdio>
#include <string>
#include <map>
#include <queue>

using namespace std;

struct node {
    string id;
    int gp, gm, gf, g;
};

map<string, int> kv;
node *students;

int main() {
    int p = 0, m = 0, n = 0, index = 0, tnum = 0;
    scanf("%d %d %d", &p, &m, &n);
    students = new node[10010];
    char tid[21];
    for (int i = 0; i < p; i++) {
        scanf("%s %d", tid, &tnum);
        index++;
        kv[tid] = index;
        students[index].id = tid;
        students[index].gp = tnum;
        students[index].gf = students[index].gm = -1;
    }

    for (int i = 0; i < m; i++) {
        scanf("%s %d", tid, &tnum);
        if (kv[tid] != 0) {
            students[kv[tid]].gm = tnum;
        }
    }
    for (int i = 0; i < n; i++) {
        scanf("%s %d", tid, &tnum);
        if (kv[tid] != 0) {
            students[kv[tid]].gf = tnum;
        }
    }

    auto cmp = [](node a, node b) { return a.g != b.g ? a.g < b.g : a.id > b.id; };
    priority_queue<node, vector<node>, decltype(cmp)> q(cmp);
    for (int i = 1; i <= index; i++) {
        if (students[i].gm > students[i].gf)
            students[i].g = (int) (0.4 * students[i].gm + 0.6 * students[i].gf + 0.5);
        else
            students[i].g = students[i].gf;

        if (students[i].gp >= 200 && students[i].g >= 60) {
            q.push(students[i]);
        }
    }

    while (!q.empty()) {
        printf("%s %d %d %d %d\n", q.top().id.c_str(), q.top().gp, q.top().gm, q.top().gf, q.top().g);
        q.pop();
    }

    return 0;
}

对于在中国大学MOOC(http://www.icourse163.org/) 学习“数据结构”课程的学生，想要获得一张合格证书，必须首先获得不少于200分的在线编程作业分，然后总评获得不少于60分（满分100）。总评成绩的计算公式为 G = (G期中x 40% + G期末x 60%)，如果 G期中 > G期末；否则总评 G 就是 G期末。这里 G期中 和 G期末 分别为学生的期中和期末成绩。 现在的问题是，每次考试都产生一张独立的成绩单。本题就请你编写程序，把不同的成绩单合为一张。

输入格式：

输入在第一行给出3个整数，分别是 P（做了在线编程作业的学生数）、M（参加了期中考试的学生数）、N（参加了期末考试的学生数）。每个数都不超过10000。 接下来有三块输入。第一块包含 P 个在线编程成绩 G编程；第二块包含 M 个期中考试成绩 G期中；第三块包含 N 个期末考试成绩 G期末。每个成绩占一行，格式为：学生学号 分数。其中学生学号为不超过20个字符的英文字母和数字；分数是非负整数（编程总分最高为900分，期中和期末的最高分为100分）。

输出格式：

打印出获得合格证书的学生名单。每个学生占一行，格式为： 学生学号 G编程 G期中 G期末 G 如果有的成绩不存在（例如某人没参加期中考试），则在相应的位置输出“-1”。输出顺序为按照总评分数（四舍五入精确到整数）递减。若有并列，则按学号递增。题目保证学号没有重复，且至少存在1个合格的学生。

输入样例：

6 6 7
01234 880
a1903 199
ydjh2 200
wehu8 300
dx86w 220
missing 400
ydhfu77 99
wehu8 55
ydjh2 98
dx86w 88
a1903 86
01234 39
ydhfu77 88
a1903 66
01234 58
wehu8 84
ydjh2 82
missing 99
dx86w 81

输出样例：

missing 400 -1 99 99
ydjh2 200 98 82 88
dx86w 220 88 81 84
wehu8 300 55 84 84

用一个结构体存储学的基本信息，包括gp（编程成绩）、gm（期中考试成绩）、gf（期末考试成绩）、g（总评成绩）、id（学生的学号）。 在输入编程成绩一块的时候，把gm和gf都初始化为-1，如果一个学生没有编程成绩，那么他的成绩肯定是不合格的。 接下来计算总评成绩的时候，把合格的学生加入到优先队列里面（优先队列是插入后按序排列的，后期可以不用排序），cmp函数按总评成绩排序，如果总评成绩相等，则按学生学号排序。 最后输出优先队列里面的学生。

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
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <cstdio>
#include <string>
#include <map>
#include <queue>

using namespace std;

struct node {
    string id;
    int gp, gm, gf, g;
};

map<string, int> kv;
node *students;

int main() {
    int p = 0, m = 0, n = 0, index = 0, tnum = 0;
    scanf("%d %d %d", &p, &m, &n);
    students = new node[10010];
    char tid[21];
    for (int i = 0; i < p; i++) {
        scanf("%s %d", tid, &tnum);
        index++;
        kv[tid] = index;
        students[index].id = tid;
        students[index].gp = tnum;
        students[index].gf = students[index].gm = -1;
    }

    for (int i = 0; i < m; i++) {
        scanf("%s %d", tid, &tnum);
        if (kv[tid] != 0) { // kv[tid] == 0表示该学生没有编程成绩
            students[kv[tid]].gm = tnum;
        }
    }
    for (int i = 0; i < n; i++) {
        scanf("%s %d", tid, &tnum);
        if (kv[tid] != 0) {
            students[kv[tid]].gf = tnum;
        }
    }

    auto cmp = [](node a, node b) { return a.g != b.g ? a.g < b.g : a.id > b.id; };
    priority_queue<node, vector<node>, decltype(cmp)> q(cmp);
    for (int i = 1; i <= index; i++) {
        if (students[i].gm > students[i].gf)
            students[i].g = (int) (0.4 * students[i].gm + 0.6 * students[i].gf + 0.5);
        else
            students[i].g = students[i].gf;

        if (students[i].gp >= 200 && students[i].g >= 60) {
            q.push(students[i]);
        }
    }

    while (!q.empty()) {
        printf("%s %d %d %d %d\n", q.top().id.c_str(), q.top().gp, q.top().gm, q.top().gf, q.top().g);
        q.pop();
    }

    return 0;
}

文本压缩有很多种方法，这里我们只考虑最简单的一种：把由相同字符组成的一个连续的片段用这个字符和片段中含有这个字符的个数来表示。例如 ccccc 就用 5c 来表示。如果字符没有重复，就原样输出。例如 aba 压缩后仍然是 aba。 解压方法就是反过来，把形如 5c 这样的表示恢复为 ccccc。 本题需要你根据压缩或解压的要求，对给定字符串进行处理。这里我们简单地假设原始字符串是完全由英文字母和空格组成的非空字符串。

输入格式：

输入第一行给出一个字符，如果是 C 就表示下面的字符串需要被压缩；如果是 D 就表示下面的字符串需要被解压。第二行给出需要被压缩或解压的不超过1000个字符的字符串，以回车结尾。题目保证字符重复个数在整型范围内，且输出文件不超过1MB。

输出格式：

根据要求压缩或解压字符串，并在一行中输出结果。

输入样例 1：

C
TTTTThhiiiis isssss a tesssst CAaaa as

输出样例 1：

5T2h4is i5s a3 te4st CA3a as

输入样例 2：

D
5T2h4is i5s a3 te4st CA3a as10Z

输出样例 2：

TTTTThhiiiis isssss a tesssst CAaaa asZZZZZZZZZZ

压缩： 维护索引i和j，i表示开始搜索的位置，如果i位置和j位置上的值相等，则j自增。否则，j-i==1时，意味着没有重复；j-i>1时，重复的次数就是j-i; 解压： 确定一个字符前面的数值具体是多少，isdigit判断一个字符是否是数字，得到time，即可输出。

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

#include <iostream>
#include <string>

using namespace std;

int main() {
    char c;
    scanf("%c", &c);
    getchar(); // \\n\\r
    string s;
    getline(cin, s);
    if (c == 'C') { // encode
        int i = 0, j = 1;
        while (i < s.length()) {
            while (j < s.length() && s[i] == s[j]) j++;
            if (j - i == 1) {
                printf("%c", s[i]);
                i = j;
                j++;
            } else {
                printf("%d%c", j - i, s[i]);
                i = j;
                j++;
            }
        }
    } else { // decode
        for (int i = 0; i < s.length(); i++) {
            int time = 0;
            while (isdigit(s[i])) {
                time = 10 * time + s[i] - '0';
                i++;
            }
            if (time != 0) {
                for (int j = 0; j < time; j++) {
                    printf("%c", s[i]);
                }
            } else {
                printf("%c", s[i]);
            }
        }
    }
    return 0;
}

给定一个 k+1 位的正整数 N，写成 ak…a1a0 的形式，其中对所有 i 有 0 <= ai < 10 且 ak > 0。N 被称为一个回文数，当且仅当对所有 i 有 ai = ak-i。零也被定义为一个回文数。 非回文数也可以通过一系列操作变出回文数。首先将该数字逆转，再将逆转数与该数相加，如果和还不是一个回文数，就重复这个逆转再相加的操作，直到一个回文数出现。如果一个非回文数可以变出回文数，就称这个数为延迟的回文数。（定义翻译自https://en.wikipedia.org/wiki/Palindromic_number） 给定任意一个正整数，本题要求你找到其变出的那个回文数。

输入格式：

输入在一行中给出一个不超过1000位的正整数。

输出格式：

对给定的整数，一行一行输出其变出回文数的过程。每行格式如下

A + B = C

其中A是原始的数字，B是A的逆转数，C是它们的和。A从输入的整数开始。重复操作直到C在10步以内变成回文数，这时在一行中输出“C is a palindromic number.”；或者如果10步都没能得到回文数，最后就在一行中输出“Not found in 10 iterations.”。

输入样例 1：

97152

输出样例 1：

97152 + 25179 = 122331
122331 + 133221 = 255552
255552 is a palindromic number.

输入样例 2：

196

输出样例 2：

196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
94039 + 93049 = 187088
187088 + 880781 = 1067869
1067869 + 9687601 = 10755470
10755470 + 07455701 = 18211171
Not found in 10 iterations.

见甲级https://www.hdvsyu.com/posts/1396/

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

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool isPalindrome(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return t == s;
}

string add(string s, string t) {
    int carry = 0;
    string result;
    for (int i = 0; i < s.length(); i++) {
        result += (s[i] + t[i] - '0' - '0' + carry) % 10 + '0';
        carry = (s[i] + t[i] - '0' - '0' + carry) / 10;
    }
    if (carry != 0) result += carry + '0';
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string s, t, sum;
    cin >> s;
    int cnt = 0;
    while (!isPalindrome(s) && cnt < 10) {
        cnt++;
        t = s;
        reverse(t.begin(), t.end());
        sum = add(s, t);
        printf("%s + %s = %s\n", s.c_str(), t.c_str(), sum.c_str());
        s = sum;
    }
    if (cnt == 10) {
        printf("Not found in 10 iterations.\n");
    } else {
        printf("%s is a palindromic number.\n", s.c_str());
    }
    return 0;
}

在浙大的计算机专业课中，经常有互评分组报告这个环节。一个组上台介绍自己的工作，其他组在台下为其表现评分。最后这个组的互评成绩是这样计算的：所有其他组的评分中，去掉一个最高分和一个最低分，剩下的分数取平均分记为 G1；老师给这个组的评分记为 G2。该组得分为 (G1+G2)/2，最后结果四舍五入后保留整数分。本题就要求你写个程序帮助老师计算每个组的互评成绩。

输入格式：

输入第一行给出两个正整数N（> 3）和M，分别是分组数和满分，均不超过100。随后N行，每行给出该组得到的N个分数（均保证为整型范围内的整数），其中第1个是老师给出的评分，后面 N-1 个是其他组给的评分。合法的输入应该是[0, M]区间内的整数，若不在合法区间内，则该分数须被忽略。题目保证老师的评分都是合法的，并且每个组至少会有3个来自同学的合法评分。

输出格式：

为每个组输出其最终得分。每个得分占一行。

输入样例：

6 50
42 49 49 35 38 41
36 51 50 28 -1 30
40 36 41 33 47 49
30 250 -25 27 45 31
48 0 0 50 50 1234
43 41 36 29 42 29

输出样例：

42
33
41
31
37
39

这里我用到了优先队列，为了去掉最小值和最大值。四舍五入的方法是将一个double的值加上0.5取它的整数部分即强制转换为int型。 见代码：

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

#include <cstdio>
#include <queue>

using namespace std;

int main() {
    int n = 0, m = 0, t = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        int g2 = 0;
        scanf("%d", &g2);
        priority_queue<int> q;
        for (int j = 0; j < n - 1; j++) {
            scanf("%d", &t);
            if (t >= 0 && t <= m) q.push(t);
        }
        q.pop(); // min
        int g1 = 0, div = q.size() - 1;
        while (q.size() > 1) {
            g1 += q.top();
            q.pop();
        }
        printf("%d\n", (int) ((g1 * 1.0 / div + g2) / 2.0 + 0.5));
    }
    return 0;
}

Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first number of the postorder traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=50000), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the first number of the postorder traversal sequence of the corresponding binary tree.

Sample Input:

7
1 2 3 4 5 6 7
2 3 1 5 4 7 6

Sample Output:

3

前序中序转后序，考试的时候还以为姥姥不会出这种题目了呢。 输出后序的第一个结点就可以了，只需在前序中序转后序的代码里面加上一个变量就可以了。见代码：

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

#include <cstdio>

int *pre, *in;

bool isOuput = false;

int find(int inl, int inr, int x) {
    for (int i = inl; i <= inr; i++) {
        if (in[i] == x) return i;
    }
    return -1;
}

void printPost(int pl, int pr, int inl, int inr, int n) {
    if (pl > pr || isOuput) return;
    int inRoot = find(inl, inr, pre[pl]);
    printPost(pl + 1, pl + inRoot - inl, inl, inRoot - 1, n);
    printPost(pl + inRoot - inl + 1, pr, inRoot + 1, inr, n);
    if (!isOuput) {
        printf("%d", in[inRoot]);
        isOuput = true;
    }
}

int main() {
    int n = 0;
    scanf("%d", &n);
    pre = new int[n];
    in = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
    }
    printPost(0, n - 1, 0, n - 1, n);
    delete[] pre;
    delete[] in;
    return 0;
}