正文

洛谷1165日志分析

author  author  2022-08-24  387

关键词：

题目描述

M 海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入库和出库的规则为先进后出，即每次出库操作出库的集装箱为当前在仓库里所有集装箱中最晚入库的集装箱。

出于分析目的，分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时，每遇到一次查询操作，都要报告出当前仓库中最大集装箱的重量。

输入输出格式

输入格式：

包含N+1 行：

第一行为1 个正整数N，对应于日志内所含操作的总数。

接下来的N 行，分别属于以下三种格式之一：

格式1: 0 X //一次集装箱入库操作，正整数X表示该次入库的集装箱的重量

格式2: 1 //一次集装箱出库操作，（就当时而言）最后入库的集装箱出库

格式3: 2 //一次查询操作，要求分析程序输出当前仓库内最大集装箱的重量

当仓库为空时你应该忽略出库操作，当仓库为空查询时你应该输出0。

输出格式：

输出行数等于日志中查询操作的次数。每行为一个正整数，表示查询结果。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于20%的数据，有N≤10；

对于40%的数据，有N≤1000；

对于100%的数据，有N≤200000，X≤108。

代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,stack[200001],top,maxl;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        maxl=0;
        scanf("%d",&m);
        if(m==0)
        {
            scanf("%d",&x);
            stack[++top]=x;
            
        }
        if(m==1)
          top--;
        if(m==2)
        {
            for(int j=1;j<=top;j++)
              if(stack[j]>maxl)
               maxl=stack[j];
            printf("%d
",maxl);
        }
    }
    return 0;
}

这个代码你会发现在提交时会tle.

为何？？

因为我们在每次进行查找时，都需要for循环一般，这样会浪费掉很多时间。

那我们该如何做呢？？

下面我们来看一下正解！

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,stack[200001],top,maxl;
int max(int i,int j)
{
    if(i>j) return i;
    else  return j;
 } 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        maxl=0;
        scanf("%d",&m);
        if(m==0)
        {
            scanf("%d",&x);
            top++;
            stack[top]=max(x,stack[top-1]);
            
        }
        if(m==1)
          top--;
        if(m==2)
        {
            printf("%d
",stack[top]);
        }
    }
    return 0;
}

是不是感觉这个代码会wa，你看这把最大的放后面肯定不对！！

这个代码是对的！

你看，我们每次输入1的时候是把最后一个数进行删除处理，而且他让输出序列中最的数，那小的数是否就没有什么用了，所以，我们只需要把最大的数放在最后面就可以啦！！

p1165日志分析

...前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入... 查看详情

[noip1997普及组]棋盘问题[洛谷]

[NOIP1997普及组]棋盘问题1.题目2.分析3.代码1.暴力枚举（时间复杂度极高）2.公式法4.总结5.更新日志1.题目设有一个方格的棋盘求出该棋盘中包含有多少个正方形、多... 查看详情

洛谷1955程序自动分析

并查集。一眼傻逼题，直接离线把一样的合并按不一样的判断即可。然后30。发现要离散。然后50。空间要开两倍。//Twenty#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath># 查看详情

洛谷p1783海滩防御分析+题解代码

洛谷P1783海滩防御分析+题解代码题目描述：WLP同学最近迷上了一款网络联机对战游戏（终于知道为毛JOHNKRAM每天刷洛谷效率那么低了），但是他却为了这个游戏很苦恼，因为他在海边的造船厂和仓库总是被敌方派人偷袭。于是，W... 查看详情

洛谷p1995程序自动分析

2017-03-18题目：https://www.luogu.org/problem/show?pid=1955这道题吗，一看就是并查集，但是范围。。。。。。好吧，加一个离散化不就好了。。。。。。不会离散化的请右转去问度娘orz1#include<iostream>2#include<cstdio>3#include<algorithm... 查看详情

洛谷p1955程序自动分析

题目描述在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1,x2,x3...代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是... 查看详情

1165:零起点学算法72——首字母变大写

1165:零起点学算法72——首字母变大写TimeLimit:1Sec MemoryLimit:64MB 64bitIOFormat:%lldSubmitted:705 Accepted:439[Submit][Status][WebBoard]Description输入一个英文句子，将每个单词的第一个字母改成大写字母。查看详情

洛谷p3707[sdoi2017]相关分析(代码片段)

题目描述Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮... 查看详情

洛谷[p1995]程序自动分析

并查集+离散化首先本题的数据范围很大,需要离散化,STL离散化代码://dat是原数据,id是编号,sub是数据的副本sort(sub+1,sub+tot+1);size=unique(sub+1,sub+tot+1)-sub-1;for(inti=1;i<=tot;i++)id[i]=lower_bound(sub+1,sub+size+1,dat[i])-sub;并查集所能维护的是具查看详情

洛谷p1854花店橱窗布置分析+题解代码

洛谷P1854花店橱窗布置分析+题解代码蒟蒻的第一道提高+/省选-，纪念一下。题目描述：某花店现有F束花，每一束花的品种都不一样，同时至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，从左到右按1到V顺序编... 查看详情

洛谷p2832行路难分析+题解代码玄学最短路

洛谷P2832行路难分析+题解代码【玄学最短路】题目背景：小X来到了山区，领略山林之乐。在他乐以忘忧之时，他突然发现，开学迫在眉睫题目描述：山区有n座山。山之间有m条羊肠小道，每条连接两座山，只能单向通过，并会耗... 查看详情

hdu1165eddy'sresearchii(数学题，递推)

//Eddy继续ProblemDescriptionAsisknown,Ackermannfunctionplaysanimportantroleinthesphereoftheoreticalcomputerscience.However,intheotherhand,thedramaticfastincreasingpaceofthefunctioncausedthevalueofAckerm 查看详情

洛谷p2194hxy烧情侣tarjan缩点分析+题解代码

洛谷P2194HXY烧情侣【Tarjan缩点】分析+题解代码题目描述：众所周知，HXY已经加入了FFF团。现在她要开始喜（sang）闻（xin）乐（bing）见（kuang）地烧情侣了。这里有n座电影院，n对情侣分别在每座电影院里，然后电影院里都有汽油... 查看详情

hdu-1165-eddy'sresearchii

这个事实上是一个递归题。题目非常easy。m的数非常小。分三种情况。算一下。就能够直接把公式算出来。当然，也能够用dp做；#include<iostream>#include<string>#include<cstdio>#include<cstring>#include<queue>#include<map>... 查看详情

洛谷p1955[noi2015]程序自动分析[并查集，离散化](代码片段)

　　题目传送门题目描述在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1,x2,x3...代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相... 查看详情

项目分析：日志分析

日志分析目的：生产中会生成大量的系统日志、应用程序日志、安全日志等日志，通过对日志的分析可以了解数据库的负载、健康状况，可以分析客户的分布情况、客户的行为，甚至基于这些分析可以做出预测。一般流程：... 查看详情

hdu1165eddy'sresearchii（给出递归公式，然后找规律）(代码片段)

-Eddy‘sresearchIITimeLimit:2000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusDescriptionAsisknown,Ackermannfunctionplaysanimportantrolei 查看详情

codeforces1165f2（二分内的check）(代码片段)

要点二分答案，内部喜闻乐见的拖延策略：对于某个打折玩具，就选最晚的打折时间买，答案并不会变劣，只是购买时间的平移。注意最晚时间不是预处理的东西，是二分内部的、在mid以内的最晚时间。#include<cstdio>#include<... 查看详情

正文