L2-1 插松枝
人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：
每人手边有一只小盒子，初始状态为空。
每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：
（1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。
（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。
（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。
输入格式：
输入在第一行中给出 3 个正整数：N（≤103），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。
随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。
输出格式：
每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
8 3 4 20 25 15 18 20 18 8 5
输出样例：
20 15 20 18 18 8 25 5
思路：把所有的松针存入一个数组，定义两个指针l,r分别表示左右边界，定义一个栈来表示盒子，定义一个队列来存储每个松枝干上松针的编号，分类讨论：
1：小盒子已经满了，但推送器上取到的松针仍然不满足要求
2：小盒子中最上面的松针不满足要求，但推送器上已经没有松针了
3：手中的松枝干上已经插满了松针
以上三种情况表示开始制作下一枚松针
当l == r 并且 盒子里面没有松针的时候，结束程序
#include <iostream> #include <cstring> #include <algorithm> #include <queue> #include <stack> using namespace std; int main() { int n, m, k; stack<int>S; queue<int>Q; cin >> n >> m >> k; while (n -- ) { int x; cin >> x; Q.push(x); } while (Q.size() || S.size()) // 元素不在栈里就在队列里面 { int cnt = 0, last = 1010; while (cnt < k) // 当前松枝干还可以继续插松针 { if(S.size() && S.top() <= last) // 栈顶元素满足要求 { cout << S.top() << ' '; last = S.top(); S.pop(); cnt ++; } else if(Q.size()) // 队列有元素 { int t = Q.front(); if(t <= last) // 队头元素满足 { cout << t << ' '; Q.pop(); last = t; cnt ++; } else if(S.size() < m) // 栈没有满 { S.push(t); Q.pop(); } else break; } else break; } cout << endl; } return 0; }
L2-2 老板的作息表
新浪微博上有人发了某老板的作息时间表，表示其每天 4:30 就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？
本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。
输入格式：
输入第一行给出一个正整数 N，为作息表上列出的时间段的个数。随后 N 行，每行给出一个时间段，格式为：
hh:mm:ss - hh:mm:ss
其中 hh、mm、ss 分别是两位数表示的小时、分钟、秒。第一个时间是开始时间，第二个是结束时间。题目保证所有时间都在一天之内（即从 00:00:00 到 23:59:59）；每个区间间隔至少 1 秒；并且任意两个给出的时间区间最多只在一个端点有重合，没有区间重叠的情况。
输出格式：
按照时间顺序列出时间表中没有出现的区间，每个区间占一行，格式与输入相同。题目保证至少存在一个区间需要输出。
输入样例：
8 13:00:00 - 18:00:00 00:00:00 - 01:00:05 08:00:00 - 09:00:00 07:10:59 - 08:00:00 01:00:05 - 04:30:00 06:30:00 - 07:10:58 05:30:00 - 06:30:00 18:00:00 - 19:00:00
输出样例：
04:30:00 - 05:30:00 07:10:58 - 07:10:59 09:00:00 - 13:00:00 19:00:00 - 23:59:59
思路：对时间表时间进行排序，用一个中间变量t来记录当前时间段的结束时间用来和上一个时间段的开始时间比较是否相等，不相等表示有空缺
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; struct node { int h1,h2,m1,m2,s1,s2; int sum1,sum2; bool operator < (const node &a) { if(sum1 != a.sum1) return sum1 < a.sum1; return sum2 < a.sum2; } }f[N]; int main() { int n; cin >> n; for(int i=0;i<n;i++) { scanf("%d:%d:%d - %d:%d:%d",&f[i].h1,&f[i].m1,&f[i].s1,&f[i].h2,&f[i].m2,&f[i].s2); f[i].sum1 = f[i].h1 * 3600 + f[i].m1 * 60 + f[i].s1; f[i].sum2 = f[i].h2 * 3600 + f[i].m2 * 60 + f[i].s2; } sort(f,f + n); int t = 0; for(int i=0;i<n;i++) { int h1 = t / 3600,m1 = (t % 3600) / 60,s1 = t % 60; int h2 = f[i].sum1 / 3600,m2 = (f[i].sum1 % 3600) / 60,s2 = f[i].sum1 % 60; if(t != f[i].sum1) printf("%02d:%02d:%02d - %02d:%02d:%02d\n",h1,m1,s1,h2,m2,s2); t = f[i].sum2; } int h1 = t / 3600,m1 = (t % 3600) / 60,s1 = t % 60; if(t != 23 * 3600 + 59 * 60 + 59) printf("%02d:%02d:%02d - 23:59:59\n",h1,m1,s1); return 0; }
L2-3 龙龙送外卖
龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。
每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……
看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。
输入格式:
输入第一行是两个数 N 和 M (2≤N≤105 , 1≤M≤105)，分别对应树上节点的个数（包括外卖站），以及新增的送餐地址的个数。
接下来首先是一行 N 个数，第 i 个数表示第 i 个点的双亲节点的编号。节点编号从 1 到 N，外卖站的双亲编号定义为 −1。
接下来有 M 行，每行给出一个新增的送餐地点的编号 Xi
。保证送餐地点中不会有外卖站，但地点有可能会重复。
为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 1，且从外卖站出发可以访问到所有地点。
注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。
输出格式:
对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。
输入样例:
7 4 -1 1 1 1 2 2 3 5 6 2 4
输出样例:
2 4 4 6
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int sum, maxx; int d[N], p[N]; int dfs(int u) { if(p[u] == -1 || d[u] > 0) return d[u]; // 当前点为根节点或者已经遍历过 sum ++ ; // 当前遍历的所有点到根节点的距离之和（已经遍历过的边只会统计一次） d[u] = dfs(p[u]) + 1; // 当前点到根节点的距离 == 父节点到根节点的距离 + 1 return d[u]; } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> p[i]; while (m -- ) { int x; cin >> x; maxx = max(maxx, dfs(x)); // 当前最大距离 cout << 2 * sum - maxx << endl; } return 0; }
L2-4 大众情人
人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 Dij；将 i 的“异性缘”定义为 1/maxj∈S(i) {Dij}，其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。
本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。
输入格式：
输入在第一行中给出一个正整数 N（≤500），为总人数。于是我们默认所有人从 1 到 N 编号。
随后 N 行，第 i 行描述了编号为 i 的人与其他人的关系，格式为：
性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K
其中 性别 是这个人的性别，F 表示女性，M 表示男性；K（<N 的非负整数）为这个人直接认识的朋友数；随后给出的是这 K 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 106的正整数。
题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。
输出格式：
第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。
输入样例：
6 F 1 4:1 F 2 1:3 4:10 F 2 4:2 2:2 M 2 5:1 3:2 M 2 2:2 6:2 M 2 3:1 2:5
输出样例：
2 3 4
