排序（变值）
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/997/G
题目描述
大概描述 由1,2,3构成一个乱序序列 每次可以改变里面的数字使得它最后变成递增或递减的样子 问最少改变多少个数字
1<n<30000
解题思路： 对于已经连续的就不用改 所以问题转化为求最大的递增或递减数;
AC代码：
#include<iostream>usingnamespacestd;intn,i,j,a,x,y,u[4]={0,0,0,0},d[4]={0,0,0,0},z=0;intmain(){cin>>n;for(i=0;i<n;i++){cin>>a;x=0;y=0;for(j=1;j<=3;j++){if(a>=j)x=max(x,u[j]+1); //记录前面最大的序列if(a<=j)y=max(y,d[j]+1);}u[a]=max(x,u[a]);d[a]=max(y,d[a]);}for(i=1;i<=3;i++){z=max(z,u[i]);z=max(z,d[i]);}n-=z;cout<<n<<endl;return0;}
携程公司氛围 125人发布