51nod 1294 修改数组

本文隶属于分类

编程语言

广告推荐

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

标签:bsp   algo   main   cstring   stream   col   body   ans   ()   

若a[i]-i(i从1开始)的值小于0,那么a[i]必须改变

若a[i]-i的值大于等于0,将a[i]-i存入新的数组中,求出新数组的最长非严格上升子序列,所得即最多的,不用改变的数。

 

技术分享图片
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<stack>
#include<iostream>
#include<algorithm>
#include<queue>
#define MAXSIZE 100005
#define LL long long

using namespace std;

int main()
{
    int s[MAXSIZE],s1[MAXSIZE];
    memset(s,0,sizeof(s));
    memset(s1,0,sizeof(s1));
    int n,len,a,ans,maxn,top;
    len = 0;
    ans = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        if(a-i >= 0)
        {
            s[len++] = a-i;
        }
        else
        {
            ans++;
        }
    }
    maxn = 0;
    top = 0;
    if(len)
        s1[top++] = s[0];
    for(int i=1;i<len;i++)
    {
        if(s[i] >= s1[top-1])
        {
            s1[top++] = s[i];
        }

        else
        {
            int pos = upper_bound(s1,s1+top,s[i]) - s1;
            s1[pos] = s[i];
        }
    }
    printf("%d\n",ans+len-top);
    return 0;
}
View Code

 

51nod 1294 修改数组

标签:bsp   algo   main   cstring   stream   col   body   ans   ()   

原文:https://www.cnblogs.com/alan-W/p/8383523.html

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

广告推荐

讨论区