Изменение любого элемента массива

Question

Учитывая массив целых чисел, вы можете изменить любое из числа произвольных положительных чисел, и в конечном итоге весь массив строго возрастает и представляет собой положительные целые числа, и попросил хотя бы изменить несколько номеров

вход: 5 1 2 2 3 4

выход: 3

и есть то, что я попробовал каждое число, с тем чтобы уменьшить больше (первое число минус один, потом второе число минус два, третье число минус три)

#include <stdio.h> 
    int Modify_the_array(int B[],int n); 
    int max(int a,int b); 
    int main(int argc,char *argv) { 

     int before_array[]={1,2,3,4,1,2,3,4,5}; 
     int len=sizeof(before_array[0])/sizeof(before_array); 
     int b; 
     b=Modify_the_array(before_array,len); 
     printf("%d\n",b); 
     return 0; 
    } 

    int max(int a,int b){ 
     return a>b?a:b; 
    } 

    int Modify_the_array(int B[],int len) { 
     int i,b=0,n=1; 
     int maxsofar,tmp,j; 
     for (i=0;i<len;i++){ 
      B[i]=B[i]-n; 
      n++; 
     } 

     maxsofar=0; 
     tmp=0; 
     for(i=0;i<len;i++) { 
      for (j=i+1;j<len;j++) { 
      if (B[j]==B[i]&&B[i]>1) { 
       maxsofar=max(maxsofar,++tmp); 
       b=len-maxsofar; 
      } 
     } 
    } 
     return b; 
} 

кто рекомендуют есть другое решение этого вопроса, более efficently, кто может дать мне несколько советов, спасибо заранее

Answer 1

я наткнулся на такую ​​же проблему в последнее время. Для того, чтобы ясно:

Постановка задачи

Задана последовательность целых чисел a1, a2, a3 ..... ап. Вы можете заменить любое целое число на любое другое положительное целое число. Сколько целых чисел необходимо заменить, чтобы сделать результирующую последовательность строго возрастающей?

Входной формат

Первая строка теста содержит целое число N - количество записей в последовательности. Следующая строка содержит N пробелов, разделенных целыми числами, где i-е целое число равно ai.

Формат вывода

Выведите минимальное количество целых чисел, которые должны быть заменены, чтобы сделать последовательность строго возрастает.

С учетом ваших данных, len = 5, arr = [1 2 2 3 4], после минуса index+1, получите [0 0 -1 -1 -1].

Игнорирование отрицательных элементов (их необходимо изменить), вычислить Longest Increasing Subsequence (неудобно для этой проблемы), что является классической проблемой динамического программирования.

Обозначить длину LIS = n (эти элементы не будут изменены). Таким образом, окончательный ответ (часть не относится к возрастающей подпоследовательности и игнорируемой отрицательной части) равна len-n (5-2 = 3).

Мы можем вычислить LIS в O (nlogn) с пространством O (n).

int solve(vector<int> &arr) { 
    int len = arr.size(); 
    for(int i = 0; i < len; i++) { 
     arr[i] -= i+1; 
    } 
    vector<int> lis(len,0); 
    int n = 0; 
    for(int i = 0; i < len; i++) { 
     if(arr[i] >= 0) { 
      int pos = binarysearchPos(lis,n,arr[i]); 
      lis[pos] = arr[i]; 
      if(n == pos) 
       n++; 
     } 
    } 
    return len-n; 
} 

int binarysearchPos(vector<int> &arr, int n, int target) { 
    if(n == 0) 
     return 0; 
    if(arr[n-1] <= target) 
     return n; 
    int low = 0, high = n-1; 
    while(low < high) { 
     int mid = (low+high)/2; 
     if(arr[mid] > target) { 
      high = mid; 
     } else { 
      low = mid+1; 
     } 
    } 
    return low; 
}