锐客网

  1. 首页 > it技术 > >

hdu5256序列严格递增

二分

题意：一个数列，a1,a2,a3,a4,---,an,需要最少修改多少个元素，使得这个序列严格递增？
a[i]-i 非递减序列 因为a[i]=a[i]，整理得a[i+1]-(i+1)>=a[i]-i。令b[i]=a[i]-i。则可以求出b[i]的最长不下降子序列的长度len，最后用n-len即为需要改变的最少的元素个数。
【hdu5256序列严格递增】

#include #include #include #include #include using namespace std; const int N=1000005; int T,n,m; int a[N]; int b[N]; int cas=1; int solve(int n){ int len=1; b[0]=a[0]; for(int i=1; i=b[len-1]) b[len++]=a[i]; else{ int pos=upper_bound(b,b+len,a[i])-b; b[pos]=a[i]; } } return len; } int main() { #ifndefONLINE_JUDGE freopen("aaa","r",stdin); #endif scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0; i



    推荐阅读


    上一篇：linux修改时间

    下一篇：数组A，有一千万个数，数组B同样也有千万多个数，然后从A和B当中随意找一个数字A1和B1,A1-B的绝对值是C，保证C最小。求A1和B1