CF605A Sorting Railway Cars
2024-10-08 00:42:16
题目大意
给出一个 1 到 n 的排列,每次操作可以将某个位置的数字移动到最前面或最后面,求将排列从小到大排序的最小操作次数
如:4 1 2 5 3 操作1:将5和3换一下变成4 1 2 3 5
操作2:将1 2 3和 4换一下变成 1 2 3 4 5 在此后即完成要求。所以最小操作次数为2。
输入:
第一行 为长度 nnn ; 第二行为原来的顺序两个数之间有空格。
输出:
最小操作次数
解题思路
因为要从小到大排序,所以我们很自然能想到lis,但是也很容易举出反例。如1 2 4 5 3,如果求lis的话答案为1,实际上答案应该是2。是因为只能将数字移动到末尾或开头。但如果是连续的数字就可以不用进行操作,所以这道题应该是求出一段连续的lis,比如上面那个数据求出的话应该是3 1 2 3 。因为数字保证是一个n的排列,所以这比直接求lis要简单,直接开个桶记录上一个有没有出现,直接进行转移即可。
代码
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 100005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int n,a[MAXN];
int dp[MAXN],ans;
bool vis[MAXN];
int main(){
n=rd();
for(register int i=1;i<=n;i++){
a[i]=rd();
vis[a[i]]=1;
if(vis[a[i]-1]) dp[a[i]]=dp[a[i]-1]+1;
else dp[a[i]]=1;
ans=max(ans,dp[a[i]]);
}
printf("%d",n-ans);
return 0;
}
最新文章
- backup log is terminating abnormally because for write on file failed: 112(error not found)
- 键盘键与虚拟键码对照表+delphi虚拟键码对应关键
- MFC 修改 单文档 SDI 窗体 标题
- jquery设置checkbox状态,设置dropdownlist选中值,隐藏某控件,给某控件追加东西
- [git]解决rebase冲突
- asp.net 操作word
- SQL Server 2008中新增的 1.变更数据捕获(CDC) 和 2.更改跟踪
- 1741. Communication Fiend(dp)
- 17.2.1 Replication Implementation Details 复制实现细节:
- bzoj3091
- JAVA面试题和答案(二)
- PowerBI 第二篇:数据建模
- R语言学习路线和常用数据挖掘包(转)
- B树和B+树详解
- Perl处理和收走子进程(退出状态码和wait)
- 【HDFS API编程】查看文件块信息
- 03 使用Tensorflow做计算题
- CODEFORCES掉RATING记 #3
- SVG 图像入门教程
- Javascript 来判断数组的假值如 null false ";"; NaN