PAT甲级题目1001 – 1020
PAT的题目，真是暗坑很多。不但要仔细审题，部分题目还要求脑筋急转弯，个别题目简直就像看悬疑片，那是：意料之外情理之中的坑……MLGB，慢慢刷着，每十道题更新一下。
以前哥只会C和CPP，现在学了python以后，发现那些专门针对C语言坑的题目，比如溢出什么的，简直就是切菜。爽翻~
顺便发现wordpress的markdown插件或者代码高亮插件的一个暗坑，就是如果你写这样的md语法：
是不会渲染成代码块的，而是会显示成这样的：
只有写成：
才能正常渲染成C++的代码~
1001 A+B format
line = [int(x) for x in input().split(' ')]
a = line[0]
b = line[1]
c = a + b
if c < 0:
negative = "-"
c = -1 * c
else:
negative = ""
c = str(c)
outs = ""
for i in range(0, int(len(c) / 3)):
outs = ("," if len(c) > 3 else "") + c[-3:] + outs
c = c[:-3]
outs = c + outs;
print(negative + outs)
1002 A+B for Polynomials
解法1
from decimal import Decimal
poly1 = input().split(' ')
poly2 = input().split(' ')
poly1 = poly1[1:]
poly2 = poly2[1:]
poly1=[Decimal(i) for i in poly1]
poly2=[Decimal(i) for i in poly2]
outpoly = []
while len(poly1) != 0 and len(poly2) != 0:
if poly1[0] == poly2[0]:
if (poly1[1] + poly2[1] != 0): #系数是0不用纳入测试节点
outpoly.append([poly1[0],poly1[1] + poly2[1]])
poly1 = poly1[2:]
poly2 = poly2[2:]
elif poly1[0] > poly2[0]:
outpoly.append([poly1[0],poly1[1]])
poly1 = poly1[2:]
else:
outpoly.append([poly2[0],poly2[1]])
poly2 = poly2[2:]
if len(poly1) != 0:
for i in range(0,len(poly1),2):
outpoly.append([poly1[i],poly1[i+1]])
if len(poly2) != 0:
for i in range(0,len(poly2),2):
outpoly.append([poly2[i],poly2[i+1]])
print( len(outpoly), end = '');
for c in outpoly:
a,n = c;
print(" {} {}".format(int(a), round(n, 1)), end='')
解法2
from decimal import Decimal
def main():
first = [Decimal(num) for num in input().split()]
first_length = first[0] * 2
first_dict = {}
first = first[1:]
for i in range(0,first_length,2):
first_dict[first[i]] = first[i + 1]
second = [Decimal(num) for num in input().split()]
second_length = second[0] * 2
second = second[1:]
for i in range(0,sencond_length,2):
if second[i] not in first_dict:
first_dict[second[i]] = second[i + 1]
else:
first_dict[second[i]] += second[i + 1]
res = []
for k, v in first_dict.items():
if v != 0: #系数是0不用纳入结果，有个测试节点
res.append((k, v))
res = sorted(res, key=lambda x: x[0], reverse=True)
print(len(res), end='')
for i in range(len(res)):
a, n = res[i]
print(" {} {}".format(int(a), round(n, 1)), end='')
# round是取小数位数的意思，还可以用下面语句来实现相同功能
print(" {} {:.1f}".format(int(a), n), end='')
if __name__ == '__main__':
main()
C++解法中的输出
cout.flags(ios::fixed);
cout.precision(1);
cout << f << endl;
或者
#include<iomanip>
using namespace std;
cout << setiosflags(ios::fixed) << setprecision(1) << f << endl;
1003 Emergency
//一个寻路问题，怎么寻都可以，关键是在路线一样短的情况下，把能招呼人较多的那一条路保存下来。
//长期不做了，先整理一下思路。就是先用一个数组把每个城市距离出发城市的距离记下来，然后遍历更新之。
//路径的维护本来也是靠数组，但因为有可能出现等长的路径，因此路径数组的每个节点不能是单元素的
//应该是多元素。先试写一下吧。
#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <functional>
using namespace std;
#define INT_MAX numeric_limits<int>::max()
struct node {//最小堆要求重载运算符，小于就可以了
int ver;
int key;//当前
node() = delete;
node(int a, int b) :ver(a), key(b) {};
bool operator < (const node &a) const { return key > a.key; } ;
//声明为const函数很重要，不然不能用。
};
using min_heap = priority_queue<node>;
int num_caculate(vector<vector<int>> &, int );
int main()
{
int city_num, road_num, mycity, emercity;
cin >> city_num >> road_num >> mycity >> emercity;
vector<vector<int>> roads(city_num, vector<int>(city_num, 0)); //定义一个二维数组用来保存路径,0表示不通
vector<int> mans(city_num); //一维数组来保存每个城市的救援队人数
//录入数据
for (int i = 0; i != city_num; ++i)
{
cin >> mans[i];
}
for (int i = 0; i != road_num; ++i)
{
int n1, n2, n3;
cin >> n1 >> n2 >> n3;
roads[n1][n2] = roads[n2][n1] = n3;
}
//录入数据完毕
vector<vector<int>> path(city_num,vector<int>()); //存储路径，表示该节点的最短上家是哪个城市
vector<int> shortest(city_num, INT_MAX); //mycity到某个city之间的距离
vector<int> mostman(city_num,0); //能收集到的最多的人数
shortest[mycity] = 0;
mostman[mycity] = mans[mycity];
min_heap vertified; //当前的最短顶点池
vertified.push(node(mycity,shortest[mycity]));
while (!vertified.empty())
{
int tmp = vertified.top().ver;
vertified.pop();
for (int i = 0; i != city_num; ++i)
{
if (roads[tmp][i])
{
if (shortest[i] > shortest[tmp] + roads[tmp][i])
{
shortest[i] = shortest[tmp] + roads[tmp][i];
vertified.push(node(i,shortest[i]));
path[i] = vector<int>(1,tmp);
if (mostman[i] < mostman[tmp] + mans[i]){
mostman[i] = mostman[tmp] + mans[i];
}
}
else if (shortest[i] == shortest[tmp] + roads[tmp][i])
{
path[i].push_back(tmp);
if (mostman[i] < mostman[tmp] + mans[i]){
mostman[i] = mostman[tmp] + mans[i];
}
}
}
}
}
int paths_avaliable = num_caculate(path,emercity);
cout << paths_avaliable << " " << mostman[emercity] << endl;
return 0;
}
int num_caculate(vector<vector<int>> &path, int endcity){
if (path[endcity].size() == 0)
return 1;
int res = 0;
for(auto c:path[endcity]){
res += num_caculate(path,c);
}
return res;
}
1004 Counting Leaves
//一个树的遍历问题，问题的关键是如何将树建立起来，这不是一个二叉树，而是N叉树，因此考虑用一个map<ID,vector<child>>
//来表示一个节点。每一层的话其实也不难，只是广度优先遍历便了。
#include<map>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
using node = map<string,vector<string>>;
int main(){
int all_nodes, nl_nodes;
cin >> all_nodes >> nl_nodes;
node tree;
queue<string> level;
for(int i = 0 ; i != nl_nodes ; ++i){
string tmp;
int n;
cin >> tmp >> n;
for(int j = 0 ; j != n ; ++j){
string tmp2;
cin >> tmp2;
tree[tmp].push_back(tmp2);
}
}
level.push(string("01"));
int level_num = 1;
vector<int> res;
while(!level.empty()){
int tmp_level_num = 0;
int this_level_no_child = 0;
for( int i = 0 ; i != level_num ; ++i){
string tmp = level.front();
level.pop();
if ((tree[tmp]).size() == 0){
++this_level_no_child;
}
for(auto c : tree[tmp]){
level.push(c);
++tmp_level_num;
}
}
level_num = tmp_level_num;
res.push_back(this_level_no_child);
}
for(int i = 0 ; i != res.size() - 1 ; ++i){
cout << res[i] << " ";
}
cout << res.back();
return 0;
}
1005 Spell It Right
def main():
num = input();
num_dict = {
"0":"zero",
"1":"one",
"2":"two",
"3":"three",
"4":"four",
"5":"five",
"6":"six",
"7":"seven",
"8":"eight",
"9":"nine",
}
res = 0;
for c in num:
res += int(c);
resstr = str(res);
outstr = ""
for c in resstr:
outstr = outstr + num_dict + " "
print(outstr.strip())
if __name__ == "__main__":
main()
1006 Sign in and Sign out
#用python写这种简单题简直就是送~
def main():
line_num = int(input())
first = ["","23:59:59"]
last = ["","00:00:00"]
for i in range(0,line_num):
line = input().split(' ')
if line[1] <= first[1]:
first[0] = line[0]
first[1] = line[1]
if line[2] >= last[1]:
last[0] = line[0]
last[1] = line[2]
print(first[0],last[0])
if __name__=="__main__":
main()
1007 Maximum Subsequence Sum
//典型的动态规划算法，最长子序列可以这么考虑。设原数组为Orign，建立数组MAX，设MAX[K]为以K结尾的最大子序列和
//那么MAX[K+1]只有两种可能，要么为Orign[K+1](当MAX[K] <= 0时)，要么为MAX[K]+Orign[K+1](当MAX[K] >= 0)时
//这么想这个问题就好解决了。
#include<stdio.h>
typedef struct nodes{
int begin;
int end;
} node;
int main(){
int K;
scanf("%d",&K);
int seq[K];
int allnegative = 1;
for (int i = 0 ; i != K ; ++i){
scanf("%d",&seq[i]);
if (seq[i] >= 0) allnegative = 0;
}
if (allnegative){
printf("0 %d %d",seq[0],seq[K-1]);
return 0;
}
int MAX[K];
node begin_end[K];
int max = MAX[0] = seq[0]; //记录已知的最大子序列和
begin_end[0].begin = begin_end[0].end = 0;
int begin = seq[0] , end = seq[0] ; //记录已知最大子序列和的开始和结束的数字
for(int i = 1 ; i != K ; ++i){
if (MAX[i-1] < 0){
MAX[i] = seq[i];
begin_end[i].begin = begin_end[i].end = i;
}else{
MAX[i] = MAX[i-1] + seq[i];
begin_end[i].begin = begin_end[i-1].begin;
begin_end[i].end = i;
}
if (MAX[i] > max){
max = MAX[i];
begin = seq[begin_end[i].begin];
end = seq[begin_end[i].end];
}
}
printf("%d %d %d",max,begin,end);
return 0;
}
1008 Elevator
#这种题目，乙级也够不上吧……
input_nums = [int(x) for x in input().split(' ')[1:]]
last_floor = 0
total_time = 0
for x in input_nums:
if last_floor <= x:
total_time = total_time + ( x - last_floor) * 6;
else:
total_time = total_time + (last_floor - x) * 4;
total_time = total_time + 5
last_floor = x
print(total_time)
1009 Product of Polynomials
#这道题坐下来只有一点，是因为对Python不熟悉造成的错误，那就是对列表元素的遍历需要调用items方法，否则将是对key的遍历
def multi(poly1,single): #把一个多项式与另一个多项式的因子相乘,poly1是一个dict，single是一个二元元组
res = dict()
for r,v in poly1.items(): #对列表元素的遍历需要调用items方法，否则将是对key的遍历
res[r+single[0]] = v * single[1]
return res
def plus(poly1,poly2): #加之后，返回第一个参数
for r,v in poly2.items(): #对列表元素的遍历需要调用items方法，否则将是对key的遍历
if r in poly1:
poly1[r] += poly2[r]
else:
poly1[r] = poly2[r]
return poly1
def main():
from decimal import Decimal
input_line1 = [Decimal(x) for x in input().split(' ')]
input_line2 = [Decimal(x) for x in input().split(' ')]
plen1 = 2 * int(input_line1[0])
plen2 = 2 * int(input_line2[0])
poly1 = dict()
poly2 = dict()
for x in range(1,plen1,2):
poly1[input_line1[x]] = input_line1[x + 1]
res_dict = multi(poly1,(input_line2[1],input_line2[2]))
for x in range(3,plen2,2):
res_dict = plus(res_dict,multi(poly1,(input_line2[x],input_line2[x + 1])))
res = []
for r,v in res_dict.items(): #对列表元素的遍历需要调用items方法，否则将是对key的遍历
if (v != 0):
res.append((r,v))
res.sort(key= lambda x:x[0],reverse = True)
print(len(res),end="")
for r,v in res:
print(" {} {}".format(int(r), round(v, 1)), end='')
if __name__=="__main__":
main()
1010 Radix
# 主要是进制转换函数
# 这个问题的天坑在于，他么的没说radix最大是37……
# 这样显然就带来一个问题，radix无法预设上限，那么就可能很大，暴力循环绝对是时间溢出
# 所以radix的下限是待转换数中最大的值，而radix上限就是已确定值的10进制
# 必须用二分法进行查找，但还有个问题。就是二分法命中以后怎么办，因为有可能值不唯一
# 二分法命中以后要在他之下的区间继续二分，直到不可再分时，radix即确定
def covert(x,radix): #把radix进制的数x转换为10进制数,x是一个字符串
res = 0
p = len(x) - 1
for c in x:
if c not in "1234567890":
c = ord(c) - ord('a') + 10
else: c = ord(c) - ord('0')
if c >= radix: #一个小坑，当C大于等于radix的时候显然要出错
return -1
res += c * pow(radix,p)
p = p - 1
return res
def find(begin,end,fix_dec,cov): #begin可能取到，end是取不到的值
least = 0 #最小可能值
if begin <= end:
mid = int((begin + end) / 2)
if covert(cov,mid) > fix_dec:
least = find(begin,mid - 1,fix_dec,cov)
elif covert(cov,mid) < fix_dec:
least = find(mid+1,end,fix_dec,cov)
else: #相等的情况要很慎重，因为有可能还有更小的
tmp = find(begin,mid - 1,fix_dec,cov) #在更小的地方继续找
if tmp == 0: #没找到
least = mid
else: least = tmp
return least
def main():
input_line = input().split(' ')
if input_line[2] == '1':
fix = input_line[0]
cov = input_line[1]
else:
fix = input_line[1]
cov = input_line[0]
fix_radix = int(input_line[3])
fix_dec = covert(fix,fix_radix)
begin = 2
end = fix_dec + 1 if fix_dec > 2 else 10
cov_radix = find(begin,end,fix_dec,cov)
if cov_radix != 0:
print(cov_radix)
else: print("Impossible")
if __name__=="__main__":
main()
1011 World Cup Betting
bets = ['L'] * 3 #每次应该赌的结果
maximum = 0
high = [0.0] * 3
chose = ['W','T','L']
for i in range(0,3):
input_seq = [float(x) for x in input().split(' ')]
for j in range(0,3):
if input_seq[j] >= high[i]:
high[i] = input_seq[j]
bets[i] = chose[j]
maximum = (high[0] * high[1] * high[2] * 0.65 - 1) * 2
print("{} {} {} {:.2f}".format(bets[0],bets[1],bets[2],maximum))
1012 The Best Rank
python解法
#首先我们用一个map来保存同学的成绩。key是ID，value是成绩的四元组，顺序为A.C.M.E
#我们将所有的成绩组织成4个数组，分别是A.C.M.E成绩。之后调用find就可以了
from fractions import Fraction
def main():
allstu,lookupstu = [int(x) for x in input().split(' ')]
students = {}
# score = [[]] * 4 这种定义方法是个坑，下面详述
score = [ [], [] , [] , []]
sorted_score = [{},{},{},{}]
A = 0
C = 1
M = 2
E = 3
course = ['A','C','M','E']
for i in range(0,allstu):
inp = [int(x) for x in input().split(' ')] #用int作key更快
avg = Fraction(inp[1] + inp[2] + inp[3] , 3)
students[inp[0]] = [avg] + inp[1:]
score[A].append(avg)
score[C].append(inp[1])
score[M].append(inp[2])
score[E].append(inp[3])
#如果接下来直接用列表搞，那开销就太大了，2000个学生就是2000*2000次的扫描，400万次
#考虑做成一个dict，2000学生时，除去sort函数，
#下面这个循环的时间复杂度只有4 * 2000 = 8000
for i in range(0,4):
score[i].sort(reverse = True)
sorted_score[i][score[i][0]] = 1
last_score = score[i][0]
for j in range(1,allstu):
if score[i][j] != last_score:
sorted_score[i][score[i][j]] = j + 1
last_score = score[i][j]
#因为放入了dict，所以接下来每次取值时，复杂度不是扫描一遍的n，而是lg(n)
for i in range(0,lookupstu):
inp = int(input())
best = 5000 #最好排名
bestcourse = -1
if inp not in students:
print("N/A")
continue
for j in range(0,4):
if sorted_score[j][students[inp][j]] < best:
best = sorted_score[j][students[inp][j]] #最好排名
bestcourse = j
print("{} {}".format(best,course[bestcourse]))
if __name__=="__main__":
main()
时间复杂度和python数列初始化暗坑
- 首先，这道题的难点应该在于数据量较大，按照最开始的思路，直接使用数列来存储成绩，之后每次调用一个数列的index()方法来做题的话，很可能导致一个不可接受的时间复杂度，接近学生数量的平方级。2000*2000的话就是400万次循环，绝对不可接受。
此时有两种思路可以解决这种问题，一个是写一个二分查找函数，就像之前写的那个radix一样，二分查找直到最小的index，第二个是用效率更高的数据结构来存储成绩和排名，自然想到了二叉树，或者最小堆之类的，把时间复杂度降下来。
因此这道题使用了用字典存储的方法，典型的字典存储应该是组织成红黑树或自平衡树之类的结构，这样就能显著降低时间复杂度。
-
这道题有个python语言的坑。
就是
score = [ [] ] * 4，这样的结果是score的4个元素实际上指向同一个列表，对任意一个元素的操作都将反映到所有元素上去，见下例：
实际上这个暗坑在Python的教材上已经提示过了，奈何没记住，白踩了一次。
1013 Battle Over Cities
//实际上是一个最大连通集问题，也就是说，一个图里有几个相互不连通的连通集，如果只有1个，那就不用修路
//如果有两个以上的最大连通集，设有N个，那就需要修N-1条路。
//最大连通集的解法就像图的遍历，关键是从一个点出发将能到达的所有点都收到一个连通集以后
//再次循环发现有不在连通集中的点，那就以这个点为出发点再次将所有他可达的点都收到一个连通集
//直到所有的点都被走过，这就确定了连通集的数量
#include <iostream>
#include <set>
#include <stack>
#include <vector>
using namespace std;
using CITY_MAP = vector<vector<int>>;
int caculate_roads(const CITY_MAP &cities, int broken_city);
int main() {
ios::sync_with_stdio(false); //关闭和stdin的同步，第一次实战用这玩意，哈哈。
int city_num, road_num, lookup_num;
cin >> city_num >> road_num >> lookup_num;
CITY_MAP cities(city_num, vector<int>(city_num, 0));
for (int i = 0; i != road_num; ++i) {
int t1, t2;
cin >> t1 >> t2;
//因为城市的号码是从1开始编号，因此需要减一
--t1;
--t2;
cities[t1][t2] = cities[t2][t1] = 1; // 1表示可通
}
//地图就初始化完了。
vector<int> results;
for (int i = 0; i != lookup_num; ++i) {
int broken_city;
cin >> broken_city;
results.push_back(caculate_roads(cities, broken_city));
}
for (auto c : results)
cout << c << endl;
return 0;
}
int caculate_roads(const CITY_MAP &cities, int broken_city) {
set<int> visited;
int city_num = cities.size();
--broken_city;
int ret = 0;
for(int i = 0 ; i != city_num ; ++i){
if ( i == broken_city or visited.find(i) != visited.end())
continue;
else{
stack<int> tmp; //典型的找最大连通集数量的算法
tmp.push(i);
++ret;
while(!tmp.empty()){
int tmp2 = tmp.top();
tmp.pop();
for(int j = 0 ; j != city_num ; ++j){
if ( j != broken_city and visited.find(j) == visited.end() and cities[tmp2][j] != 0){
visited.insert(j);
tmp.push(j);
}
}
}
}
}
return ret - 1; //要修的路是连通集数量-1
}
1014 Waiting in Line
//这道题是假设所有人8点一口气都到了，然后排着队一个一个办业务，要求输出的是谁的业务几点办完。
//模拟一下窗口的排队情况就行了。
//这道题算是1017 Queueding at bank的预演版，那道题整体思路差不多，但坑要多一些。
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
struct node {
int index;
int time;
int done;
node() = default;
node(const int &a, const int &b, const int &c) : index(a), time(b), done(c){};
}; //单个顾客，index表示其序列号，time表示他需要的时间，done表示他结束的时间
void print_time(map<int, node> &result,int index);
int main() {
ios::sync_with_stdio(false);
int N, M, K, Q;
cin >> N >> M >> K >> Q;
queue<node> cus;
vector<int> query(Q);
for (int i = 0; i != K; ++i) {
int tmp;
cin >> tmp;
cus.push(node(i, tmp, -1));
}
for (int i = 0; i != Q; ++i) {
cin >> query[i];
}
vector<queue<node>> windows(N); //总共N个窗口，也就是最后有N个队列。
int inqueue = 0; //就下面这个循环体用。
for (int i = 0; i != M; ++i) {
for (int j = 0; j != N; ++j) {
if (inqueue >= K)
break; //表示用户还不足以填满窗口
else {
windows[j].push(cus.front());
cus.pop();
}
++inqueue;
}
}
//这样队列就被填满了，以下开始正式计算
map<int, node> result;
vector<int> last_finish_time(N, 0); //每个窗口有一个最后一个人完成的时间
int now; //现在的时间
result[1] = cus.front();
//计算的方式就是模拟队列。
while (true) {
int min = 65535, minwindow = -1;
for (int i = 0; i != N; ++i) { //寻找当前队列中第一个完成的
if (!windows[i].empty() and
last_finish_time[i] + windows[i].front().time < min) {
//如果相等的话自然选中序列号最小的队列
min = windows[i].front().time + last_finish_time[i];
minwindow = i;
}
}
if (minwindow == -1) //所有队列为空
break;
else {
windows[minwindow].front().done =
last_finish_time[minwindow] + windows[minwindow].front().time;
last_finish_time[minwindow] = windows[minwindow].front().done;
result[windows[minwindow].front().index] = windows[minwindow].front();
windows[minwindow].pop();
if (!cus.empty()) {
windows[minwindow].push(cus.front());
cus.pop();
}
}
}
for(auto c:query){
print_time(result,c - 1);
}
return 0;
}
void print_time(map<int, node> &result,int index){
int done = result[index].done;
if (done - result[index].time >= (17 - 8) * 60){
cout << "Sorry"<< endl;
return ;
}
int hour = 8 + done / 60 ;
int minute = done % 60;
cout << (hour < 10 ? "0" : "") << hour << ":" << (minute < 10 ? "0" : "") << minute << endl;
}
1015 Reversible Primes
#可反序的素数，有两个考点，一个是进制转换。实际上是先将数字转换为radix为进制的字符串，再逆转
#在转换为10进制，看是不是素数。
from math import sqrt,pow
def is_su(test):
if test < 2: return False
if test == 2 or test == 3: return True
for i in range(2,int(sqrt(test) + 1)):
if test % i == 0:
return False
return True
def convertfrom10(i,to): #因为题目保证to小于10，简化了处理
"""
将数字i从10进制转换为to进制
"""
ret = ""
q,r = divmod(i,to)
ret = str(r) + ret
while q != 0:
q,r = divmod(q,to)
ret = str(r) + ret
return ret
def convertto10(i,fro):
"""
将数字i从fro进制转换为10进制
"""
ret = 0
j = len(i) - 1
for x in i:
ret += int(x) * pow(fro,j)
j -= 1
return int(ret)
def main():
while True:
line = [int(x) for x in input().split(' ')]
if line[0] < 0:
break
else:
tmp = convertfrom10(line[0],line[1])
tmp = "".join(reversed(tmp))
rev = convertto10(tmp,line[1])
if is_su(line[0]) and is_su(rev):
print("Yes")
else:
print("No")
if __name__=="__main__":
main()
1016 Phone Bills
python解法
# 要是考试真遇到这道题我都考虑放弃，光做各种格式处理就要把自己恶心死了
# 考虑用一个dict来保存每个人的情况，key为name,value为所有的电话的数组
# 之后对每一个key的数组进行排序，排序的key为时间。之后直接进行一遍梳理
# 如果on-line后面不是off-line，或者off-line前面不是on-line，一律删除
# 之后逐小时进行处理。再维护一个新的dict，key是name，
# value是[(begintime,endtime,minutes,money),...]
# 之后进行输出。不可能跨月，因为不给年份的话，2月无法处理。
ONLINE = 0
OFFLINE = 1
stat = {
"on-line": ONLINE,
"off-line": OFFLINE,
}
def get_all_calls(call_num):
ret = dict()
for i in range(0, call_num):
line = [x for x in input().split(' ')]
line[2] = stat[line[2]]
if line[0] in ret:
ret[line[0]].append(line[1:])
else:
ret[line[0]] = [line[1:]]
return ret
def flitter_calls(raw_calls):
"""
将结果过滤，把不匹配的结果删除，并返回已经匹配的新字典
新字典的key是用户名，value是[begintime,endtime]
"""
ret = dict() # 一个新的字典。
for c in raw_calls:
raw_calls.sort(key=lambda x: x[0]) # 按时间先后排序，这里跨天什么的都没问题
last_stat = OFFLINE
last_call_begin = ""
ret = []
for call in raw_calls: # 现在call是一个二元数组，call[0]表示时间，call[1]表示状态
if call[1] == ONLINE:
last_call_begin = call[0]
last_stat = ONLINE
else:
if call[1] != last_stat:
last_stat = 1 - last_stat
if call[1] == OFFLINE and call[0] != last_call_begin:
ret.append([last_call_begin, call[0]])
return ret
def caculute(calls, price):
ret = dict()
month = -1
for name in calls: # 要记得，calls[name] 是一个列表之列表，即[[],[]]这样的形式
if len(calls[name]) == 0: # 表示没有有效结果
continue
ret[name] = []
for record in calls[name]:
minutes = 0
fee = 0
month, bdd, bhh, bmm = [int(x) for x in record[0].split(':')]
month, edd, ehh, emm = [int(x) for x in record[1].split(':')]
while True:
if edd - bdd > 1:
minutes += (edd - bdd - 1) * 24 * 60
fee += sum(price) * 60 * (edd - bdd - 1)
bdd = edd - 1
elif edd - bdd == 1:
minutes += (60 - bmm) + (24 - bhh - 1) * 60
fee += sum(price[bhh+1:]) * 60 + (60 - bmm) * price[bhh]
bdd = edd
bhh = 0
bmm = 0
else:
if bhh == ehh:
minutes += emm - bmm
fee += price[ehh] * (emm - bmm)
break
else:
minutes += 60 - bmm
fee += price[bhh] * (60 - bmm)
bmm = 0
bhh += 1
# while 语句结束了
ret[name].append([record[0][3:], record[1][3:], minutes, fee / 100])
month = str(month) if month > 10 else "0" + str(month)
return month, ret
def main():
price = [int(x) for x in input().split(' ')]
call_num = int(input())
raw_calls = get_all_calls(call_num)
calls = flitter_calls(raw_calls)
month, calls = caculute(calls, price)
for name in sorted(calls):
print(name, month)
total = 0.0
for record in calls[name]: # calls[name]是一个[[begin,end,minutes,fee],...]列表
print("{} {} {} {:.2f}".format(record[0], record[1], record[2], record[3]))
total += record[3]
print("Total amount:{:.2f}".format(total))
if __name__ == "__main__":
main()
一些测试数据
这道题其实只要把复杂的格式转换搞定了，结果就并不难，但仍然在细节处理上出现了失误，这里提供几组数据用来测试。
#样例1
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
2
CYLL 02:01:05:59 on-line
CYLL 02:02:01:00 off-line
#样例2
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
2
CYLL 02:01:05:59 on-line
CYLL 02:20:01:00 off-line
#样例3：
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
2
CYLL 02:01:01:59 on-line
CYLL 02:01:01:59 off-line
对python解题的一点感慨
这道题里涉及了复杂的数据结构嵌套，比如dict的value，是[[begin,end,minutes,fee],...]这样的结构。在处理的过程中，这样的嵌套会使得代码过长且不容易理解，而且因为python的数据结构成员都是未命名的，不像我用c++声明一个struct{int begin;int end;int minute;int fee}，可以很直观地用.运算符来取所需的数据，这就导致python的数据结构在在使用时经常要通过纯数字下标记忆一个列表的元素到底是干什么的，真是特别费脑筋的一件事情，如果用类似C语言的#define来定义常量，又失去了python数据结构灵活的特点。
这样的代码如果不加足够明确的注释，后来人看起来应该非常懵逼，肯定不好维护。
1017 Queueing at Bank
C++解法
//考虑用一个struct来表示不同的顾客，同时将每个人的时间转换为一个int，其值为距离当天0点的秒数
// struct包括：到达时间、需要时间、完成时间。
//用一个最小堆保存顾客，之后做一排序。得到按顺序的人群。
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
struct Customer {
int arrivetime;
int servicetime;
int requiretime;
int endtime;
Customer() = default;
Customer(const string &a, int b) : requiretime(b * 60) {
int hh = stoi(string(a.begin(), a.begin() + 2));
int mm = stoi(string(a.begin() + 3, a.begin() + 5));
int ss = stoi(string(a.begin() + 6, a.end()));
arrivetime = hh * 3600 + mm * 60 + ss;
}
bool operator<(const Customer &a) const { return arrivetime < a.arrivetime; }
};
struct be_greater {
bool operator()(const Customer &a, const Customer &b) const { return b < a; }
};
using min_heap = priority_queue<Customer, vector<Customer>, be_greater>;
int main() {
ios::sync_with_stdio(false);
min_heap customers;
int cus_num, win_num;
cin >> cus_num >> win_num;
for (int i = 0; i != cus_num; ++i) {
string tmps;
int tmpi;
cin >> tmps >> tmpi;
customers.push(Customer(tmps, tmpi));
}
const int opentime = 8 * 3600; //银行的开张时间和关门时间
const int closetime = 17 * 3600;
int now = opentime;
int wait_time_sum = 0;
int served_custom = 0;
vector<bool> win_avaliable(win_num, true);
vector<Customer> win_in_service(win_num);
while (true) { //又想起1016有个哥们的解法是逐分钟计算大法，真是叹为观止。
for (int i = 0; i != win_num; ++i) {
//这个循环功能很简单，就是有窗口空闲的话，我们就弹出一个用户，将他填入窗口
if (win_avaliable[i] and !customers.empty()) {
if (customers.top().arrivetime > closetime)
//剩余队列中最早到达的已经超过17点，直接跳出即可。
break;
win_avaliable[i] = false;
win_in_service[i] = customers.top();
win_in_service[i].servicetime = win_in_service[i].arrivetime > now
? win_in_service[i].arrivetime
: now;
//上面这句话的意思是，如果此人的到达时间比now晚，那他的服务时间就是到达时间；
//否则就是他已经到达了，那么他的服务时间就是now
customers.pop();
}
}
int min = 10017 * 3600; //最早完成的那个窗口什么时候完成，之所以设置成这么一个值，原因见解读
int first_finish_window = -1; //最早完成的窗口是哪个
for (int i = 0; i != win_num; ++i) { //找到几个窗口中最早完成的那个
if (!win_avaliable[i]) {
if (win_in_service[i].servicetime + win_in_service[i].requiretime <
min) {
min = win_in_service[i].servicetime + win_in_service[i].requiretime;
first_finish_window = i;
}
}
}
if (min == 10017 * 3600) //表示三个队列全是空的
break;
//到这里，我们已经找到了最早完成的那个窗口，接下来处理之
win_avaliable[first_finish_window] = true;
win_in_service[first_finish_window].endtime = min;
wait_time_sum += win_in_service[first_finish_window].servicetime -
win_in_service[first_finish_window].arrivetime;
served_custom += 1;
now = min;
}
cout.flags(ios::fixed);
cout.precision(1);
cout << wait_time_sum / 60.0 / served_custom << endl;
return 0;
}
附测试节点及思路
思路很简单，就是模拟窗口的运行，一个用户到了以后，如果有空窗口，就使用这个窗口。这道题的一些小坑及测试节点如下:
#样例一，每个人来了以后窗口都没人。也就是说人不是一个接一个来的，中间会有空隙
3 1
07:55:00 16
08:59:59 15
10:01:00 60
#样例二，所有的人都是临近下班时到的，需要的时间还都很长，导致最后一个人处理完到零点以后了
#也因此我的min设置成了10017*3600，是按一口气来了10000人，所有人都需要1小时的最长时间算的
#这也提醒我们，设置min的时候设置成numeric_limits<int>::max()最稳妥
10 1
16:59:10 60
16:59:11 60
16:59:12 60
16:59:13 60
16:59:14 60
16:59:15 60
16:59:16 60
16:59:17 60
16:59:18 60
16:59:19 60
1018 Public Bike Management
C++解法1
//我的思路是暴力的，首先是用单源有权最短路算法把最短路算出来。在计算时，普通的寻路算法因为不需要考虑等长
//路径的情况，因此path[]的值是之前一个节点，而因为这道题要考虑路径相等的可能性，因此path[]的值是上一个
//可能节点的集合。
//得到这样一条path之后，我就用把所有可能的路径都暴力求出来，保存在一个shortest_path变量下。
//这个变量的每一个值都是一条从0开始到达目的地的路径。
//之后我对这样的路径集合进行遍历，找到需要带出和带回的最小自行车数量
//之后再对这样的路径集合进行一次遍历，找到带出最小自行车数的路径的序号。
//如果这个序号唯一，那么直接输出结果就行，如果序号不唯一，那么再在其中寻找最小带回自行车数量。
//最后就是输出了。
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
#define INT_MAX numeric_limits<int>::max()
void path_caculate(vector<vector<int>> &path, int sta, vector<int> single_path);
vector<vector<int>> shortest_path; //一个全局变量，用来保存最短路径
int main() {
ios::sync_with_stdio(false);
int cap, sta_count, ill_sta, road_num;
cin >> cap >> sta_count >> ill_sta >> road_num;
vector<int> stations(sta_count + 1, INT_MAX); // 0号节点是PBMC
for (int i = 1; i != sta_count + 1; ++i) {
cin >> stations[i];
}
vector<vector<int>> maps(sta_count + 1, vector<int>(sta_count + 1, 0));
for (int i = 0; i != road_num; ++i) {
int t1, t2, t3;
cin >> t1 >> t2 >> t3;
maps[t1][t2] = maps[t2][t1] = t3;
}
//以上数据就录入完了。现在开始做寻路
vector<vector<int>> path(sta_count + 1); //加一万万不能忘
vector<int> min(sta_count + 1, INT_MAX); //指示了每个节点当前最短路径
min[0] = 0;
vector<int> visited(sta_count + 1, 0);
for (;;) {
int dmin = INT_MAX;
int dnum = -1;
for (int i = 0; i != sta_count + 1; ++i) {
if (min[i] <= dmin and visited[i] == 0) {
dmin = min[i];
dnum = i;
}
}
if (dnum == -1)
break;
visited[dnum] = 1;
for (int i = 0; i != sta_count + 1; ++i) {
if (!visited[i] && maps[i][dnum] != 0) {
if (min[i] > min[dnum] + maps[dnum][i]) {
min[i] = min[dnum] + maps[dnum][i];
path[i] = vector<int>(1, dnum);
} else if (min[i] == min[dnum] + maps[dnum][i]) {
path[i].push_back(dnum);
}
}
}
}
//此时最短路径就求完了，我们可以知道到ill_sta到底哪条路最近了。
//然后我们把这些路径都求出来。
path_caculate(path, ill_sta, vector<int>());
//此时shortest_path已经被填满
vector<int> take_out(shortest_path.size());
vector<int> take_back(shortest_path.size());
int min_take_out = INT_MAX;
int min_take_back = INT_MAX;
for (int i = 0; i != shortest_path.size(); ++i) {
int now_left = 0;
int take = 0;
for (int j = 0; j != shortest_path[i].size(); ++j) {
if (stations[shortest_path[i][j]] + now_left < cap / 2) {
//就是现在站点的车加上你带过来的，还不足一半，那就调高带出来的车的数量
take += cap / 2 - stations[shortest_path[i][j]] - now_left;
now_left = 0;
} else {
//现在站点的车加上带过来的，刚好一半甚至超了一半，take显然不用变，但now_left就要增加了
now_left += stations[shortest_path[i][j]] - cap / 2;
}
}
if (take < min_take_out)
min_take_out = take;
take_out[i] = take;
take_back[i] = now_left;
}
vector<int> equal_take_out; //最少带出
for (int i = 0; i != shortest_path.size(); ++i) {
if (take_out[i] == min_take_out) {
equal_take_out.push_back(i);
}
}
if (equal_take_out.size() == 1) {
int index = equal_take_out[0];
cout << take_out[index] << " " << 0;
for (auto x : shortest_path[index]) {
cout << "->" << x;
}
cout << " " << take_back[index] << endl;
} else { //这里贡献了一个出错点，下面提供的测试节点1不过
for (auto index : equal_take_out) {
if (take_back[index] < min_take_back)
min_take_back = take_back[index];
}
for (auto index : equal_take_out) {
if (take_back[index] == min_take_back) {
cout << take_out[index] << " " << 0;
for (auto x : shortest_path[index]) {
cout << "->" << x;
}
cout << " " << take_back[index] << endl;
}
}
}
return 0;
}
void path_caculate(vector<vector<int>> &path, int sta,
vector<int> single_path) {
//该算法中，0节点不会进入队列
if (sta == 0) {
shortest_path.push_back(
vector<int>(single_path.rbegin(), single_path.rend()));
//因为singel_path是反的，这里把他弄正了
return;
} else {
single_path.push_back(sta);
for (auto x : path[sta]) {
path_caculate(path, x, single_path);
}
}
}
测试节点
#1，不过的原因是有些take_out不是最小但是take_in是最小
10 5 4 8
9 9 9 0 9
0 1 1
0 2 1
0 4 4
1 3 2
2 5 1
5 3 1
3 4 1
2 1 0
#2,非标准djstrila算法可能遇到的错误，主要是计算了完全相同的重复路径
10 9 8 14
1 1 1 1 1 1 1 1 0
0 1 8
0 2 2
2 3 2
3 4 2
4 1 2
0 5 4
5 1 4
0 6 5
6 1 3
0 7 3
7 1 4
0 9 8
9 8 1
1 8 1
本人的两个出错点及对djstrila算法的一些思考
出错点一：非标准算法导致的重复路径问题。
我的算法是：维护一个最小堆，之后将出发节点先加入该最小堆中，之后再对所有邻接点进行求值，之后将邻接点加入该堆中，从堆中弹出一个最小的节点，之后重复上述过程。这样的算法虽然可能导致同一个节点A被反复推入堆中，但是因为该节点A的最短路径确定之前，他并不会被弹出堆。因此，等他弹出堆的时候，他的最短路径必然已经确定了，这是因为djs算法是由近及远进行求解、且没有负权路径来保证的的，如果某一个节点A被弹出后，还有另外一个节点B到他的距离使得他的路径更短，那么那个节点V应该已经在最小堆中被弹出过，并更新了A的距离。因此当节点A被弹出用来计算和他邻接的节点的距离时，他的最短距离已经确定了。假设之前他有个更大的距离被加入了最小堆，该值会在之后弹出，但不会更新任何邻接点的数据，所以也无伤大雅。
但是在本题中，因为要求路径，两次弹出A节点（如上述测试样例#2），会出现一次min[i] == min[tmp] + maps[tmp][i]，也就是说所有和A的邻接节点的path路径，将会记录两次A，即path[i] = {A,A}。这样在最后计算得出的shortest_path中，会出现两条完全一样的路径。这其实本身也无伤大雅，但在最后输出的时候，如果最短路径刚好经过A，就会在输出代码中输出两次结果，测试节点就无法通过了。
#include <queue>
#include <vector>
#include <functional>
struct node {
int index;
int weight;
node(const int &a, const int &b) : index(a), weight(b){};
bool operator<(const node &a) const { return weight < a.weight; };
bool operator>(const node &a) const { return weight > a.weight; };
};
using min_heap = priority_queue<node, vector<node>, greater<node>>;
//以上是最小堆的准备工作
vector<vector<int>> path(sta_count + 1);
vector<int> min(sta_count + 1, INT_MAX);
min_heap vertex;
vertex.push(node(0, 0));
min[0] = 0;
//以上是最小堆的初始化
while (!vertex.empty()) {
int tmp = vertex.top().index;
vertex.pop();
for (int i = 0; i != sta_count + 1; ++i) {
if (maps[tmp][i] != 0) {
if (min[i] > min[tmp] + maps[tmp][i]) {
min[i] = min[tmp] + maps[tmp][i];
vertex.push(node(i, min[i]));
path[i] = vector<int>(1, tmp);
} else if (min[i] == min[tmp] + maps[tmp][i]) {
path[i].push_back(tmp);
}
}
}
}
//以上是具体算法
这个错误在本题中可以通过在最后的输出代码中加一个break来完成，如：
if (equal_take_out.size() == 1) {
int index = equal_take_out[0];
cout << take_out[index] << " " << 0;
for (auto x : shortest_path[index]) {
cout << "->" << x;
}
cout << " " << take_back[index] << endl;
} else {
for (auto index : equal_take_out) {
if (take_back[index] < min_take_back)
min_take_back = take_back[index];
}
for (auto index : equal_take_out) {
if (take_back[index] == min_take_back) {
cout << take_out[index] << " " << 0;
for (auto x : shortest_path[index]) {
cout << "->" << x;
}
cout << " " << take_back[index] << endl;
}
break; //这个break保证了重复路径只输出一次
}
}
也可以通过纠正上面的djs算法来保证正确，具体方式是采用一个visited[]数组，直接将重复路径排除掉，如：
vector<bool> visited(sta_count + 1,false);
while (!vertex.empty()) {
int tmp = vertex.top().index;
vertex.pop(); //无论如何，都是要pop掉的，不然会无限循环
if (visited[tmp]) //已经弹出过的节点不允许弹出第二遍。
continue;
else visited[tmp] = true;
for (int i = 0; i != sta_count + 1; ++i) {
if (maps[tmp][i] != 0) {
if (min[i] > min[tmp] + maps[tmp][i]) {
min[i] = min[tmp] + maps[tmp][i];
vertex.push(node(i, min[i]));
path[i] = vector<int>(1, tmp);
} else if (min[i] == min[tmp] + maps[tmp][i]) {
path[i].push_back(tmp);
}
}
}
}
出错点二：求最短最出和带回时的错误
题目的要求实际上分三层：1.选路径最短的；2.如果路径等长，那么选带出最少的；3.如果带出数量还一样，那么选带回最少的。因此，有些等长的路径可能存在：某些带出很多，但带回是0，某些带出0，但带回很多。也就是可能不存在一条路径，刚好带回0也带出0。所以在计算时必须注意，在比带回数量时，要求带出数量是相等的才比带回数量。
DFS算法
//这道题的另外一个思路是直接用深度优先遍历。就是从0出发，直接暴力求解到需要维护站点
//的所有可能路径，然后维护一个可能路径的最短长度、最少带出、最少带回值。
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
#define INT_MAX numeric_limits<int>::max()
void dfs(const vector<vector<int>> &maps, const int ill, const int sta_count,
const int cap, const vector<int> &stations, vector<bool> visited,
int start, int &minlen, int &min_take_out, int &min_take_back,
int thislen, int this_take_out, int this_take_back,
vector<int> temppath, vector<int> &path);
int main() {
ios::sync_with_stdio(false);
int cap, sta_count, ill_sta, road_num;
cin >> cap >> sta_count >> ill_sta >> road_num;
vector<int> stations(sta_count + 1, INT_MAX); // 0号节点是PBMC
for (int i = 1; i != sta_count + 1; ++i) {
cin >> stations[i];
}
vector<vector<int>> maps(sta_count + 1, vector<int>(sta_count + 1, 0));
for (int i = 0; i != road_num; ++i) {
int t1, t2, t3;
cin >> t1 >> t2 >> t3;
maps[t1][t2] = maps[t2][t1] = t3;
}
vector<bool> visited(sta_count + 1, false);
int minlen = INT_MAX; //所有路径中到达ill_station最短的
int min_take_out = INT_MAX; //所有路径中带出的最小车数量
int min_take_back = INT_MAX; //所有路径中带回的最小车数量
int thislen = INT_MAX; //到目前节点为止的路径长度
int this_take_out = 0; //到目前节点为需要带出的车数量
int this_take_back = 0; //到目前节点为止需要带回的车数量
vector<int> temppath;
vector<int> path;
dfs(maps, ill_sta, sta_count, cap, stations, visited, 0, minlen, min_take_out,
min_take_back, thislen, this_take_out, this_take_back, temppath, path);
//因为path、minlen,min_take_out,min_take_back是引用，因此已经被更新了
//话说引用也有不好，不看声明你都不知道哪些参数会被改变
cout << min_take_out << " " << 0;
path = vector<int>(path.begin() + 1 , path.end()); //把0节点跳过
for (auto x:path){
cout << "->" << x;
}
cout << " " << min_take_back << endl;
return 0;
}
void dfs(const vector<vector<int>> &maps, const int ill, const int sta_count,
const int cap, const vector<int> &stations, vector<bool> visited,
int start, int &minlen, int &min_take_out, int &min_take_back,
int thislen, int this_take_out, int this_take_back,
vector<int> temppath, vector<int> &path) {
//递归函数，遍历所有可能到达需维护站点的路径。因为不想用全局变量，真是传了无数个参数啊
//不过能不用全局变量我就不用全局变量，哈哈，我就是这么任性。
visited[start] = true;
temppath.push_back(start);
if (start == ill) { //遍历找到了需要维护的节点
if (thislen < minlen) { //这条路径的len更短一些
minlen = thislen;
min_take_out = this_take_out;
min_take_back = this_take_back;
path = temppath;
} else if (thislen == minlen) { //这条路径的len一样长
if (this_take_out < min_take_out) { //但带出的自行车少
min_take_out = this_take_out;
min_take_back = this_take_back;
path = temppath;
} else if (this_take_out == min_take_out and
this_take_back < min_take_back) {
//即带出的自行车一样，但带回的自行车少
min_take_back = this_take_back;
path = temppath;
}
}
return; //每次遍历到ill就没有继续遍历的必要了
}
for (int i = 1; i != sta_count + 1; ++i) {
if (!visited[i] and maps[start][i] != 0) {
int after_i_take_out = this_take_out, after_i_take_back = this_take_back;
if (this_take_back + stations[i] < cap / 2){
after_i_take_out += cap / 2 - this_take_back - stations[i];
after_i_take_back = 0;
}else{
after_i_take_back += stations[i] - cap / 2;
}
dfs(maps,ill,sta_count,cap,stations,visited,i,minlen,min_take_out,
min_take_back, thislen + maps[start][i], after_i_take_out, after_i_take_back, temppath, path);
}
}
}
两个节点的AC图
很少放AC图吧，但是这道题实在把我折磨坏了，两个AC的算法时间复杂度明显第二个要好一点。第二种算法似乎也可以作为一种最短路算法。只是把path换成一个路径的集合即可，只需要改动一点代码：
vector<vector<int>> paths; //每个元素都是一个vector，记录着一个最短路径
void dfs(args...){
...;
if (start == ill) {
if (thislen < minlen) {
paths = vector<int>(1,temppath); //重写整个paths
} else if (thislen == minlen) {
paths.push_back(temppath); //改为push_back就行
}
}
...;
}
原代码AC图：
DFS代码AC图：
1019 General Palindromic Number
Python解法
# 这道题的关键是怎么表示一个回文数，就是用数字。但不是单个数字了，比如说12进制里，就可能出现11
# 但这里的11被认为是B这样的一个代词，是单个数字的。
def trans_to_base(dec, base):
if dec == 0:
return [0]
result = []
while dec != 0:
dec, r = divmod(dec, base)
result.append(r)
return result
def main():
dec, base = [int(x) for x in input().split(' ')]
res = trans_to_base(dec, base)
rev = [x for x in reversed(res)] #这里有个小坑
if res == rev:
print("Yes")
else:
print("No")
for i in range(0,len(rev) - 1):
print(rev[i],end = " ")
print(rev[-1])
if __name__=="__main__":
main()
python的reversed()函数
python的reversed()函数得到的结果并不是原类型，而是一个可迭代对象。举例如下：
因此，任何试图直接a == reversed(a)的行为都将出错，也不能直接使用b = reversed(a)来试图生成一个与a同类型的逆序实例。
1020 Tree Traversals
//给一个后序遍历、中序遍历，让给出层序遍历的结果。
//所以重点在于把这个树建立起来。层序遍历就手到擒来了。
//后序遍历是左右根，中序遍历是左根右。
//因为树的定义都是递归定义的，因此算法写成递归更简洁。
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {
int num;
node *left;
node *right;
};
node *build_tree(vector<int> postorder, vector<int> inorder);
vector<int> level_travel(node *root);
int main() {
int len;
cin >> len;
vector<int> postorder(len);
vector<int> inorder(len);
for (int i = 0; i != len; ++i)
cin >> postorder[i];
for (int i = 0; i != len; ++i)
cin >> inorder[i];
node *root = build_tree(postorder, inorder);
vector<int> output = level_travel(root);
for(int i = 0 ; i != output.size() - 1 ; ++i){
cout << output[i] << " ";
}
cout << *output.rbegin() << endl;
return 0;
}
node *build_tree(vector<int> postorder, vector<int> inorder) {
if (postorder.empty()) {
return nullptr;
}
node *root = new node;
root->num = postorder.back();
auto root_place_in_inorder = find(inorder.begin(), inorder.end(), root->num);
vector<int> left_tree_inorder =
vector<int>(inorder.begin(), root_place_in_inorder);
vector<int> right_tree_inorder =
vector<int>(root_place_in_inorder + 1, inorder.end());
vector<int> left_tree_postorder = vector<int>(
postorder.begin(), postorder.begin() + left_tree_inorder.size());
vector<int> right_tree_postorder = vector<int>(
postorder.begin() + left_tree_inorder.size(), postorder.end() - 1);
root->left = build_tree(left_tree_postorder, left_tree_inorder);
root->right = build_tree(right_tree_postorder, right_tree_inorder);
return root;
}
vector<int> level_travel(node *root) {
vector<int> res;
queue<node *> nodes;
int level_num = 1; //每一层的节点数
int next_level_num = 0; //下一层的节点数
nodes.push(root);
while (!nodes.empty()) {
while (level_num != 0) {
--level_num;
node *tmp = nodes.front();
nodes.pop();
res.push_back(tmp->num);
if (tmp->left) {
nodes.push(tmp->left);
++next_level_num;
}
if (tmp->right){
nodes.push(tmp->right);
++next_level_num;
}
}
level_num = next_level_num;
next_level_num = 0;
}
return res;
}
0 条评论