刪數問題

給定n位正整數a，去掉其中任意k個數字后，剩下的數字按原次序排列組成一個新的正整數。對于給定的n和k，設計一個算法，找出剩下數字組成的新數最少的刪數方案。

輸入示例： 178543 4

輸出： 13

輸入示例： 56317 3

輸出： 17

分析：

每一步總是選擇一個使剩下的數最小的數字刪除。

即按高位到低位的順序搜索，若各位數字遞增，則刪除最后一個數字；否則刪除第一個遞減區間的首字符。

刪除之后，其他數字往前移動一位，填補位置。

最后把剩下的幾個數字，組成一個整數。

#include

#include

int main()

{

int a,n,k; //n指a有多少位

int i,j,s=1;

scanf("%d",&a); //a為輸入的整數

scanf("%d",&k); //刪去k個數字

n=log10(a)+1;

int p[n];

j=a;

for(i=n-1;i>=0;i--){ //數組p中從0到n-1,分別為：5 6 3 1 7

p[i]=j%10;

j/=10;

}

for(i=1;i<=k;i++){ //控制刪去的個數

for(j=0;j

if(p[j]

continue;

}else{ //如果遞減，刪除第一個數

p[j]=-1;

break;

}

}

for(j=0;j

if(p[j]==-1){ //都往前挪

p[j]=p[j+1];

p[j+1]=-1;

}

}

}

for(i=0;i

printf("%d",p[i]);

}

return 0;

}

運行截圖

總結

以上是生活随笔為你收集整理的python贪心算法求删数问题_贪心算法删数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。