提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

hdu5256序列变换（非递减子序列）

序列 变换 递减
2023-09-11 14:14:00 时间
题意（中文直接粘吧）
序列变换


Problem Description
    我们有一个数列A1,A2...An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。
请输出最少需要修改多少个元素。
 
Input
第一行输入一个T(1≤T≤10)，表示有多少组数据
每一组数据：
第一行输入一个N(1≤N≤105)，表示数列的长度
第二行输入N个数A1,A2,...,An。
每一个数列中的元素都是正整数而且不超过106。

Output
对于每组数据，先输出一行

Case #i:

然后输出最少需要修改多少个元素。
 
Sample Input
2
2
1 10
3
2 5 4


思路：
      比较有意思的一个题，我的第一反应是n-上升子序列，这样显然不对，因为1 2 3 3 4 5这样就是6-5=1，那个多出来的3怎么改都不行的，其实可以这样转化问题，我们把每个数字都对应减去他们的位置编号，比如
1   2   4  6   9   8
-1 -2  -3 -4  -5  -6
这样得到
0 0 1 2 5 2

这样做到底为了什么呢？就是为了排除相等的情况，第i个位置最少要比i+1个位置少1，而i最少要比i+2的位置少2，这样的话，我们只要全部减去自己位置的编号就相当于直接处理好了所有的位置关系，处理好之后我们就直接n-最大非递减子序列就行了，非递减子序列可以按找递增子序列的那个方法弄，简单改下就行，还有注意可以用二分贪心的那个方法，普通暴力的方法会超时吧N*N的。总体的时间复杂度是O(n*log(n))的没啥压力。


#include<stdio.h>
#include<string.h>

#define N 100000 + 100

int num[N] ,now[N];

int main ()
{
    int t ,cas = 1 ,i ,n;
    int low ,up ,mid ,len;
    scanf("%d" ,&t);
    while(t--)
    {
        scanf("%d" ,&n);
        for(i = 1 ;i <= n ;i ++)
        {
            scanf("%d" ,&num[i]);
            num[i] -= i;
        }
        len = 1;
        now[1] = num[1];
        for(i = 2 ;i <= n ;i ++)
        {
            low = 1 ,up = len;
            while(low <= up)
            {
                mid = (low + up) >> 1;
                if(now[mid] <= num[i])
                low = mid + 1;
                else up = mid - 1;
            }
            now[low] = num[i];
            if(low > len) len ++;
        }
        printf("Case #%d:\n" ,cas ++);
        printf("%d\n" ,n - len);

    }
    return 0;
}



相关文章