首页 > 其他分享 >P10155题解

P10155题解

时间:2024-08-19 20:24:58浏览次数:12  
标签:排列 cout int 题解 元素 maxn 操作 P10155

1 题意

给定一个排列 p p p,每次可以选择一个数 p i p_i pi​,将它插入到它之后的第一个大于它的数之前,最小化使整个排列单调不降的次数,若无法做到,输出 -1

2 分析

先说无解的情况,如果排列中最大的元素不在最后一个,那么最大的元素之后没有比它大的元素,就无法进行操作,故无解。

在有解的情况下,考虑贪心思路,从倒数第二大的元素开始操作,若该元素之后没有比它小的元素,就不进行操作,若有比它小的元素,就进行操作,因为该元素是为进行操作的元素中最大的,所以会将它插入到所有未进行操作的元素的后面,从而保证排列的有序性。

3 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[2000005],b[2000005],maxn,ans;
int main()
{
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    maxn=max(maxn,a[i]);//求排列中的最大值
  }
  if(a[n-1]!=maxn)//判断无解
  {
    cout<<-1;
    return 0;
  }
  b[n-1]=INT_MAX;
  for(int i=n-2;i>=0;i--)
  {
    b[i]=min(b[i+1],a[i+1]);//求该元素之后的所有元素中的最小值
    if(a[i]>b[i])ans++;//判断是否进行操作
  }
  cout<<ans;
  return 0;
}

标签:排列,cout,int,题解,元素,maxn,操作,P10155
From: https://blog.csdn.net/Zhou2010_/article/details/141334177

相关文章

  • AT_abc027_b题解
    说明需要掌握贪心算法。这么简单为什么是黄题啊?题意给定一个长度为的非负整数序列,你可以进行若干次操作,每次操作都可以选择一个长度为的子串,花费的代价,将其中的每个数都变成该子串的平均值,现在你必须将每个数都变成相同的,你必须同时保证每个数为非负整数。分析先算......
  • 题解:「ROI 2017 Day 2」存储器
    题目信息题目链接LuoguP10653、LOJ2770题目描述给定一个字符串\(S\),设其长度为\(n\),每个字符要么是+要么是-。定义一个片段为\(S\)的一个子串\(S[l,r]\)满足下面三个条件:\(l=1\)或者\(S_{l-1}\neS_l\)。\(r=n\)或者\(S_{r+1}\neS_r\)。\(S_l=S_{l+1}=......
  • P6218 [USACO06NOV] Round Numbers S 题解
    题面题目传送门如果一个正整数的二进制表示中,00的数目不小于11的数目,那么它就被称为「圆数」。例如,99的二进制表示为10011001,其中有22个00与22个11。因此,99是一个「圆数」。请你计算,区间[l,r][l,r]中有多少个「圆数」。前置芝士1.数位dp相关的题:P4317花神......
  • [题解]UVA1127 Word Puzzles
    UVA1127WordPuzzles我们对模式串建立AC自动机,然后就比较板子了,只需要把\(8\)个方向都跑一遍匹配就可以了。时间复杂度是\(O(T\times8nm)\)。注意输入是大写字母。点击查看代码#include<bits/stdc++.h>#defineK1010//模式串个数&矩阵长宽#defineN1000010//节点个......
  • el-table使用sortablejs推拽排序卡顿问题解决
    使用sortablejs拖拽el-table排序时,对于纯文本表格,正常使用即可,不会卡顿initSort(){consttbody=document.querySelector('.el-table__body-wrappertbody')const_this=thisSortable.create(tbody,{draggable:'.el-table__row',......
  • 【题解】Solution Set - NOIP2024集训Day10 树的直径、重⼼、中⼼
    【题解】SolutionSet-NOIP2024集训Day10树的直径、重⼼、中⼼https://www.becoder.com.cn/contest/5464「CF516D」DrazilandMorningExercise首先,我们可以换根求出所有点的\(f\)。然后不会了……思考一下,一条直径提供的到底时什么。实际上,一条直径上的点取到\(f\)......
  • Vue 项目报错Uncaught SyntaxError: Unexpected token < 刷新之后又可以继续访问问题解
    场景:页面打开不操作,前端项目代码更新重新部署后(比如Jenkins发布部署)页面不刷新,操作页面(点击打开弹窗、切换菜单等),页面没有反应,控制台报错 UncaughtSyntaxError:Unexpectedtoken<。这个问题偶现,只有在项目重新部署后会出现,页面刷新后就恢复正常 问题原因:在前端项目未更......
  • 题解:牛客周赛 Round 56(A-E)
    A面包店故事题面小镇上有一家面包店,面包以\(x\)元的价格出售,加\(y\)元可以多加几块培根。小歪带着\(n\)元来到了面包店,他想知道自己能不能买到加培根的面包?输入在一行上输入三个整数\(x,y,n\left(1\lex,y,n\le100\right)\)代表面包的价格、培根的价格和小歪带的......
  • P1540 [NOIP2010 提高组] 机器翻译 题解
    题目概括给定N个整数,和一个容量为M的“字典”,从头到尾依次翻译,每次翻译先看自家字典,没有的话再看别人的字典并存到自家字典,如果自家字典满了,当前单词的翻译会代替最早进入的。做题思路定义一个长度为M的字典数组,依次遍历N个数,每次翻译先检索字典数组,没有的话加入字典并......
  • 题解:P10844 [EGOI2024] Infinite Race / 无限赛跑
    题解:P10844[EGOI2024]InfiniteRace/无限赛跑有n个人在环形跑道上跑步,和q次超越别人或被别人超越,别人要么在Anika前面,要么在后面怎么说呢,建议降红由于只有重复超过一个人才肯定是跑过一圈的,所以一个数组就行了,每超过一次就打上标记,不然去掉标记。#include<bits/stdc......