首页 > 其他分享 >I 排序

I 排序

时间:2023-11-11 22:24:06浏览次数:41  
标签:le 数字 int 张卡牌 卡牌 ans 排序

A


Description:

  • 一叠卡牌有 \(n\) 张,每张卡牌上面写有一个数字,从上往下数第 \(i\) 张卡牌上面写的数字为 \(a_i\),每张卡牌上面写的数字互不相等,并且数字都在 \([1, n]\) 的范围内。现在要把卡牌整理成顺序卡牌(卡牌堆从上到下第 \(i\) 张卡牌上面写着数字 \(i\) )。 可是这叠卡牌被诅咒过,对卡牌的操作只能按以下规则执行:
  • 选择牌堆中任意一张卡牌,从卡牌堆中抽出,并将其放置于牌堆顶。
  • 请问最少需要执行几次这样的操作可以将卡牌整理成顺序卡牌

Constraints:

  • \(1\le n \le 3 \times 10^5\)
  • \(1\le a_i \le n\)
  • \(\forall i,j(1\le i \lt j \le n)\),$a_i \neq a_j $

Analysis:

  • 最多要进行 \(n-1\) 次操作,只要某个数比前面小,就要调整顺序,故可以从后遍历,找到最长的接续序列,如 \(n,n-1,n-2,···\),最小操作次数即为总长度减去该序列的长度。

Solution:

void solve() {
	int n; cin >> n;
	vector<int> v;
	for(int i=0;i<n;i++) {
		int x; cin >> x;
		v.push_back(x);
	}
	int ans = n;
	for(int i=n-1;i>=0;i--) {
		if(v[i] == ans) ans --;
	}
	cout << ans << endl;
}

标签:le,数字,int,张卡牌,卡牌,ans,排序
From: https://www.cnblogs.com/Trilliverse/p/17826455.html

相关文章

  • MySQL 数据库查询与数据操作:使用 ORDER BY 排序和 DELETE 删除记录
    使用ORDERBY进行排序使用ORDERBY语句按升序或降序对结果进行排序。ORDERBY关键字默认按升序排序。要按降序排序结果,使用DESC关键字。示例按名称按字母顺序排序结果:importmysql.connectormydb=mysql.connector.connect(host="localhost",user="yourusernam......
  • MySQL 数据库查询与数据操作:使用 ORDER BY 排序和 DELETE 删除记录
    使用ORDERBY进行排序使用ORDERBY语句按升序或降序对结果进行排序。ORDERBY关键字默认按升序排序。要按降序排序结果,使用DESC关键字。示例按名称按字母顺序排序结果:importmysql.connectormydb=mysql.connector.connect(host="localhost",user="youruserna......
  • 冒泡排序(Bubble Sort)
    目录1.冒泡排序1.1基本原理1.2例子1.3示例代码2.魔炮排序2.1基本原理2.1例子2.2示例代码1.冒泡排序1.1基本原理冒泡排序(BubbleSort)是一种简单的排序算法。它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直......
  • 数据结构之树(二叉排序树)
    特点二叉排序树(BinarySearchTree,BST)的特点:每个节点最多有两个子节点,分别称为左子节点和右子节点。节点的左子树中的所有节点的值都小于该节点的值。节点的右子树中的所有节点的值都大于该节点的值。左子树和右子树也分别是二叉排序树。BST的主要优点是可以实现高效的查......
  • MATLAB对矩阵按照某一列排序
    转载:matlab对矩阵按照某一列排序_matlab对矩阵按列升序排列-CSDN博客升序排列:命令:data=[1,2,3;7,8,9;4,5,6];a1=sortrows(data,1);%按照第一列排序(升序),其他列与排序结果一一对应。a2=sortrows(data,2);%按照第二列排序(升序),其他列与排序结果一一对应......
  • C++简单插入排序
    voidinsertSort(inta[],intlen){ inti,j,temp; if(len==1)return; for(i=1;i<len;i++){ if(a[i]<a[i-1]){ temp=a[i]; for(j=i-1;j>=0&&a[j]>temp;j--){ a[j+1]=a[j]; }a[j+1]=temp; ......
  • C++创建二叉排序树
    voidcreate(Tree&t,intval){if(t==nullptr){t=newnode;t->data=val;t->left=t->right=nullptr;}elseif(val>t->data)create(t->right,val);elseif(val<t->data)create(t->left,val);}voidinsert(Tree&......
  • C#的DataTable排序各种方法
    在很多时候,我们做datatable排序的时候,在string类型 需要进行数字转换在排序的时候,就不能用自带的,dtTemplate.DefaultView.Sort办法,这时候的排序需要先转换类型,在进行排序。下面介绍几种转换类型后排序的方法:第一种:     publicDataTableLinqSortDataTable(DataT......
  • 冒泡排序
    voidbubble(int*arr,intn){ for(inti=1;i<=n-1;i++) { intflag=1; for(intj=1;j<=n-i;j++) { if(arr[j]>arr[j+1]) { inttemp; temp=a......
  • 牛客[编程题] HJ26 字符串排序
    HJ26 字符串排序  中等  通过率:39.52%  时间限制:1秒  空间限制:32M 描述编写一个程序,将输入字符串中的字符按如下规则排序。规则1:英文字母从A到Z排列,不区分大小写。如,输入:Type输出:epTy规则2:同一个英文字母的大小写同时存在时,按照输入......