首页 > 其他分享 >CF381B题解

CF381B题解

时间:2024-09-06 10:49:52浏览次数:10  
标签:CF381B 题意 int 题解 down vis vector 100010

我们先理解题意,大致意思是:
给你一个序列让你组成一个中间有一个数,左侧递增右侧递减的数列。
从这道题的题意来看,大概思路是:
1. 我们要将最大值设为中间的数,然后左右两端尽可能的小。
2. 跑两遍循环,分别为左边的递增边的递减。
3. 还有,因为一个数可以出现很多次,我们需要一个 vis 数组来存储此位置是否被使用过。
4. 最后,我采用的是开两个 vector 来存储左边的上升,和右边的下降。
AC 代码

#include<bits/stdc++.h>
using namespace std;
int a[100010];
bool vis[100010];
vector<int> up;//上升部分 
vector<int> down;//下降部分 
int main(){
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    sort(a+1,a+m+1);
    down.push_back(a[m]);
    vis[m]=true;
    for(int i=m-1;i>=1;i--){
        if(a[i]<a[i+1]){
            down.push_back(a[i]);
            vis[i]=true;
        }
    }
    int top=0;
    for(int i=1;i<=m;i++){
        if(vis[i]!=true&&a[i]>top&&a[i]<a[m]){
            vis[i]=true;
            top=a[i];
            up.push_back(a[i]);
        }
    }
    cout<<up.size()+down.size()<<endl;
    for(int i=0;i<up.size();i++){
        cout<<up[i]<<" ";
    }
    for(int i=0;i<down.size();i++){
        cout<<down[i]<<" ";
    }
    return 0;
}


代码较为丑陋,仅供参考。
完结撒花。

标签:CF381B,题意,int,题解,down,vis,vector,100010
From: https://blog.csdn.net/WJX120423/article/details/141953243

相关文章

  • 2024 年高教社杯全国大学生数学建模竞赛B题解题思路(第一版)
    原文链接:https://www.cnblogs.com/qimoxuan/articles/18399372赛题:问题1:抽样检测方案设计分析:抽样检测方案需要在保证决策准确性的同时,尽量减少检测成本。需要考虑抽样误差对决策的影响,以及如何设置抽样大小和接受/拒绝标准。解题思路:1.确定抽样方法:采用属性抽样,......
  • 【洛谷 P1449】后缀表达式 题解(栈+分支)
    后缀表达式题目描述所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。如:对应的后缀表达式为:。在该式中,@为表达式的结束符号。.为操作数的结束符号。输入格式输入一行......
  • CodeForces 2009G Yunli's Subarray Queries 题解
    云璃!高质量Div.4,吊打某些Div.2Only/Edu/Div.3。本题是下面四道题目的有机结合,优雅且经典。LuoguP4168[Violet]蒲公英|LuoguP1997faebdc的烦恼|LuoguP3203[HNOI2010]弹飞绵羊|LuoguP3246[HNOI2016]序列建议先完成这四题。(必须指出:用蒲公英的分块方......
  • P3688 [ZJOI2017] 树状数组 题解
    P3688[ZJOI2017]树状数组题解记录一下做这道题的心路历程,说明在没有事先知道“九条是求成了后缀和”的情况下如何发现,以及解释一些部分分的做法。sub1,18pts:暴力搜索无脑枚举,复杂度\(\mathcalO(n^m)\)。代码:#include<bits/stdc++.h>#defineintlonglong#defineloop......
  • AT_arc151 题解 & 数组字典序大小比较求方案数
    很好的一题,做的时候没有一点思路,看了题解。看来做过的题目还是太少了,记录一下经验。注意到$1\leN\le2\times10^5$和$1\leM\le10^9$,如此庞大的数据,dp是肯定不行的。当字典序$A<B$时,当且仅当存在$i$,使得$\forallx\in[1,i)$,$A_x=B_x$且$A_i<B_i$。那么我们对于$......
  • CF704B Ant Man 题解
    题目传送门前置知识预设性DP解法考虑统计每个数单独的贡献,然后进行预设性DP。设\(f_{i,j}\)表示当前填了\([1,i]\)时有\(j\)个连续段的最小权值,边界为\(f_{0,0}=0\)。对\(i(i\nes,i\nee)\)填入的位置进行分讨。新开一段后面填入的数都比\(i\)大(如果存......
  • 洛谷 P1516 青蛙的约会 题解
    一道简单的数学题~首先分析题意。精简得出:假设跳了\(t\)次,那么青蛙A的坐标是\((x+mt)\modL\),青蛙B的坐标是\((y+nt)\modL\),列出方程:\[x+mt\equivy+nt\pmodL\]由于余数具有可减性,所以把\(y+nt\)移到左边,得出:\[x-y+mt-nt\equiv0\pmodL\]写成人话:\[(x-y+mt-nt)\mod......
  • 9.5 上午 becoder 模拟赛总结 & 题解
    T1文本编辑器说实话,看到题目的第一瞬间,我还以为gm第一道就放了平衡树。一道链表的模板题,当然愿意也可以用平衡树写,不多说了,直接放代码(100pts):#defineN1000005chars[N],t[N];intnow,pre[N],nxt[N];intmain(){scanf("%s%s",s+1,t+1);intn=strlen(s+1);......
  • 【转载】P1399 [NOI2013] 快餐店 题解
    作者%%%%%%NightTide%%%%%%题目大意求一棵基环树的重心。即一个点,使得树上到其距离最长的点到其的距离最短。注意,这个点不一定是一个节点,可以在树上的任意位置。输出树上到其距离最长的点到其的距离。或者说求基环树最短的直径?(大雾解题思路显然,这颗基环树的直径只有两......
  • [USACO13OPEN] Photo G 题解
    前言题目链接:洛谷。题意简述一个长度为\(n\)的序列,有一些位置染了色。现给出\(m\)条限制,第\(i\)条限制为\(l_i\simr_i\)中有且仅有一个位置染色。求出满足这\(m\)中条件,染色位置个数最多为多少。\(n\leq2\times10^5\),\(m\leq10^5\)。题目分析方法\(1\):差......