题目描述 现有数列A_1,A_2,\cdots,A_NA1,A2,⋯,AN，修改最少的数字，使得数列严格单调递增。
输入格式 第1 行，1 个整数N
第2 行，N 个整数A_1,A_2,\cdots,A_NA1,A2,⋯,AN
输出格式 1 个整数，表示最少修改的数字
输入输出样例 输入 #1复制 3 1 3 2 输出 #1复制 1 说明/提示 • 对于50% 的数据，N \le 10^3N≤103
• 对于100% 的数据，1 \le N \le 10^5 , 1 \le A_i \le 10^91≤N≤105,1≤Ai≤109
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int main(){ int n,ans=1; scanf("%d",&n); int a[n],sa[n]; for(int i=0;i<n;i++) scanf("%d",&a[i]); sa[ans]=a[0]; for(int tz,i=1;i<n;i++){ if(sa[ans]<a[i]){ ans++; sa[ans]=a[i]; }else{ tz=lower_bound(sa,sa+ans,a[i])-sa; sa[tz]=a[i]; } } printf("%d",n-ans); return 0; }