题意
给出n个数,求出修改最少的数字,使得数列严格单调递增。
思路
我们用一个数组s来记录当前存到的数字,每次放进一个数字,我们就判断它是不是比之前的数小,否则我们就二分找到一个最好的位置可以放下它。
代码
#include<cstdio>
int n,s[100001],a,tot,ans;
inline int ef(int x)
{
int l=1,r=tot,mid;
while(l<r)
{
mid=(l+r)>>1;
if (s[mid]>=x) r=mid;
else l=mid+1;
}
return l;
}
int main()
{
scanf("%d",&n);
scanf("%d",&a);
s[++tot]=a;
for (int i=1;i<n;i++)
{
scanf("%d",&a);
if (a<s[tot]) {s[ef(a)]=a; ans++;}
else s[++tot]=a;
}
printf("%d",ans);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)