L2-041 插松枝??题目链接
题目描述
人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：
- 每人手边有一只小盒子，初始状态为空。
- 每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
- 工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
- 工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
- 当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：
（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
分析：模拟题，按照题意往下写就行，麻烦的是判断太多，我的起手思路是根据succ数组中有无树叶开始，因为题目里虽然说每次起手都从小盒子里拿，但是如果succ中有树叶，不需要考虑小盒子里的树叶，因为小盒子里的top树叶就是上一次不满足条件才放进去的，所以直接从传送带上拿就可以，之后再展开判断就可以，题目思路很多这只是我的一种想法，
大佬看看就行。然后报段错误是访问了空的queue或者stack，例如直接访问queue.front()这样就会报错，解决方案是在前面加判断非空
while（!queue.empty() ）queue.front();
AC代码
#include<bits/stdc++.h>
using namespace std;
stack<int>box;
vector<int>succ;
queue<int>con;
int n,m,k,i;
void coutt()
{
for( i =0; i<succ.size()-1; i++)
cout<<succ[i]<<" ";
cout<<succ[i]<<endl;
succ.clear();
}
int main()
{
cin>>n>>m>>k;
int mark=0;
while(n--)
{
int x;
cin>>x;
con.push(x);
}
while(!con.empty())
{
//小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。
if(!box.empty()&&!succ.empty())
if(box.size()==m&&box.top()>succ.back()&&con.front()>succ.back())
coutt();
if(succ.size()==k)//手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
coutt();
if(succ.empty())
{
if(box.empty())
{//box里面没树叶，从传送带上拿;
succ.push_back(con.front());
con.pop();
}
else
{//box里有值,循环从box里取树叶;
while(1)
{
if(succ.size()==k)
{
coutt();break;
}
if(!succ.empty())
{//如果succ不为空
if(succ.back()>=box.top())
{
succ.push_back(box.top());
box.pop();
}
else//box里的不满足退出循环，从传输带上取树叶;
break;
}
else
{//如果succ为空;
succ.push_back(box.top());
box.pop();
}
if(box.size()==0)//连续从box里面取值，防止取空;
break;
}
}
}
else
{//不为空的时候，不用考虑从box里取值；直接从传送带上取;
if(succ.back()>=con.front())
{
succ.push_back(con.front());
con.pop();
}
else
{
box.push(con.front());
con.pop();
}
}
}
//小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。
if(succ.size()>0&&!box.empty())
coutt();
//清空box
while(!box.empty())
{
if(succ.size()==k)//手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
coutt();
if(succ.empty())
{
succ.push_back(box.top());
box.pop();
}
else
{
if(succ.back()>=box.top())
{
succ.push_back(box.top());
box.pop();
}
else
coutt();
}
}
//输出最后一个
if(succ.size()>0)
coutt();
return 0;
}
L2-042 老板的作息表?题目链接
题目描述：
新浪微博上有人发了某老板的作息时间表，表示其每天 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分析：简单的结构体排序，根据每段前面的时间排序，n的范围，如果是开一个结构体数组的话需要计算一下最坏的情况是多大，24*60*60=86400（题目已经说了是最小间隔是1秒），这里建议开一个vector<struct> 不需要考虑存不下的情况； 坑点是排完序之后还需要判断第一个的第一个时间是不是00:00:00，最后一个的第二个时间是不是23:59:59，在循环前后特判一下就可解决；
AC代码
#include<bits/stdc++.h>
using namespace std;
struct in
{
string s1,s2;
}frontt;
int n;
vector <struct in>ans;
int cmp(struct in a,struct in b)
{
return a.s1<b.s1;
}
int main()
{
cin>>n;
while(n--)
{
cin>>frontt.s1;
scanf(" - ");
cin>>frontt.s2;
ans.push_back(frontt);
}
sort(ans.begin(),ans.end(),cmp);
if(ans[0].s1!="00:00:00")
cout<<"00:00:00"<<" - "<<ans[0].s1<<endl;
for(int k=1;k<ans.size();k++)
if(ans[k].s1!=ans[k-1].s2)
cout<<ans[k-1].s2<<" - "<<ans[k].s1<<endl;
if(ans[ans.size()-1].s2!="23:59:59")
cout<<ans[ans.size()-1].s2<<" - "<<"23:59:59"<<endl;
return 0;
}
L2-043 龙龙送外卖?题目链接
题目描述：
龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。
每到中午 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分析：范围10^5不能直接dfs去找最短路，时间超限，也不能直接从根节点往下找符合条件的节点集合，（这道题卡时间卡的很严），所以这道题的思路是从下往上找，找到根节点返回，记录所有经过的节点数，最后的答案是：节点数*2-max(节点深度)，时间优化是在递归回溯的时候把深度记录，下次在访问到的时候就不用往下继续去找。
AC代码
#include<bits/stdc++.h>
using namespace std;
set<int>sett;
int n,m;
int deep[100001]= {0};
int fa[100001];
int maxx;
void findd(int x)
{
if(sett.find(x)!=sett.end())//遇到之前走过的点就不往下走了
{
deep[x]=deep[ fa[x] ]+1;//记录深度
return ;
}
sett.insert(x);//记录经过节点数，去重
if(fa[x]==-1)
{
deep[ x ]=1;
return ;
}
else
{
findd( fa[x] );
deep[x]=deep[ fa[x] ]+1;//回溯的时候记录深度
}
}
int main()
{
cin>>n>>m;
deep[1]=1;
for(int i=1; i<=n; i++)
{
int x;
cin>>x;
fa[i]=x;
}
while(m--)
{
int x;
cin>>x;
findd(x);
maxx=max(maxx,deep[x]-1);
cout<<(sett.size()-1)*2-maxx<<endl;
}
return 0;
}
