次序组成一个新的正整数。编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数 最小。输出应包括所去掉的数字的位置和组成的新数。 例如:N=’178543’,S=4,删数过程如下: 算法分析:因为N<=80,所以以字串形式输入N,使用尽可能逼近目标的贪心法来逐 删去其中S个数符,每一步总是选择一个使剩下的数最小的数符删去。之所以作出这样贪心 的选择,是因为删S个数符的全局最优解,包含了删一个数符的子问题的最优解 为了保证删1个数符后的数最小,我们按高位→低位的方向搜索递减区间。若不存在递 减区间,则删尾数符;否则删递减区间的首字符,这样形成一个新数串。然后回到串首,重 复上述规则,剩下一数符……依此类推,直到删除S个数符为止。程序如下: #include <stdio. h> #include <string. h int main( char a[81],c[81] int b[80] int len, lenl, s, sl, t.k. i printf("Input the number N: scanf ("%s", a) printf( The wish deletes numbers: " scanf(%d", &s) len= len1= strlen(a) for(i =0; i< len-1: i++) forj=i+1: j< len; j++) if(clj] >c[k])k=j: c[k]=0 [t++]=k while(s) for(i =0: i< len: i++) if(a[i+1]>a[k])k=i+1 for(i k: i< len: i++) a[i]=a[i+1]8 次序组成一个新的正整数。编程对给定的 N 和 S，寻找一种方案使得剩下的数字组成的新数 最小。输出应包括所去掉的数字的位置和组成的新数。 例如： N=’178543’, S=4，删数过程如下： 178543 → 17543 → 1543 → 143 → 13 算法分析：因为 N<=80，所以以字串形式输入 N，使用尽可能逼近目标的贪心法来逐一 删去其中 S 个数符，每一步总是选择一个使剩下的数最小的数符删去。之所以作出这样贪心 的选择，是因为删 S 个数符的全局最优解，包含了删一个数符的子问题的最优解。 为了保证删 1 个数符后的数最小，我们按高位→低位的方向搜索递减区间。若不存在递 减区间，则删尾数符；否则删递减区间的首字符，这样形成一个新数串。然后回到串首，重 复上述规则，剩下一数符……依此类推，直到删除 S 个数符为止。程序如下： #include <stdio.h> #include <string.h> int main() { char a[81],c[81]; int b[80]; int len,len1,s,s1,t,k,i,j; printf("Input the number N:"); scanf("%s",a); printf("The wish deletes numbers: "); scanf("%d",&s); len = len1 = strlen(a); t = 0; s1 = s; for(i = 0; i<len; i++) c[i] = a[i]; for(i = 0; i < len-1; i++) { k = i; for(j = i+1; j < len; j++) if(c[j] > c[k]) k = j; c[k] = 0; b[t++] = k; } while(s) { k=0; for(i = 0; i < len; i++) if(a[i+1] > a[k]) k = i+1; for(i = k; i < len; i++) a[i] = a[i+1]; --len; --s;