题目描述
键盘输入一个高精度的正整数 $N$，去掉其中任意 $k$ 个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的 $N$ 和 $k$ ，寻找一种方案使得剩下的数字组成的新数最小。
输出应包括所去掉的数字的位置和组成的新的整数。（ $N$ 不超过 $250$ 位） 输入数据均不需判错。
输入格式
$n$(高精度的正整数)
$k$(需要删除的数字个数)
输出格式
最后剩下的最小数。
样例输入
175438
4
样例输出
13
Solution
这道题是贪心算法经典问题，思路：每次都选取一个使得剩下的数最小的数字。
注意：每次都选取最大的数字是错误的！
我因为这个错了5次
废话不多说，代码简单易懂，直接上代码
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
char a[260],b[260],k[260];
int p;
scanf("%s",a);
cin>>p;
while(p>=1){
for(int i=0;i<strlen(a);i++){
strcpy(k,a);
for(int j=i;j<strlen(a);j++){
k[j]=k[j+1];
}
int j=0;
int d;
sscanf(k,"%d",&d);
if(d!=0){
while(k[j]=='0'){
for(int t=j;t<strlen(a)-1;t++){
k[t]=k[t+1];
}
j++;
}
}
if(i==0) {
strcpy(b,k);
continue;
}
if(strlen(b)>strlen(k)) {
strcpy(b,k);
continue;
}
if(strcmp(b,k)>0){
strcpy(b,k);
}
}
strcpy(a,b);
p--;
}
cout<<a;
}
|
