UC知道删数问题 贪心法
来源：百度知道 编辑：UC知道 时间：2024/05/02 11:53:04
“按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字母。”
就这句想不明白。
键盘输人一 个高精度的正整数N，去掉其中任意s个数字后剩下的数字按原左右次序组成—个新的正整数．编程对给定的N和s，寻找一种方案使得剩下的数字组成的新数最小．
输出应包括所去掉的数字的位置和组成的新的正整数．(N不超过240位)
输人数据均不需判错．
我这些问的是同一题。我知道要怎样删，但不明白为什么要这样删。llxy7只是跟我说明怎样删，而没有告诉我为什么要这样删。为什么要这样删才是我这题要问的。
就这句想不明白。
键盘输人一 个高精度的正整数N，去掉其中任意s个数字后剩下的数字按原左右次序组成—个新的正整数．编程对给定的N和s，寻找一种方案使得剩下的数字组成的新数最小．
输出应包括所去掉的数字的位置和组成的新的正整数．(N不超过240位)
输人数据均不需判错．
我这些问的是同一题。我知道要怎样删，但不明白为什么要这样删。llxy7只是跟我说明怎样删，而没有告诉我为什么要这样删。为什么要这样删才是我这题要问的。
原来你想问的是为什么要这么删啊。
整题答案：
#include <iostream>
#include <string>
using namespace std;
void main()
{
string num;
unsigned int S;
cout << "Input your N";
cin >> num;
cout << "Input your S";
cin >> S;
for(unsigned int j = 0; j < S; j++)
{
for(unsigned int i = 0; i < num.size(); i++)
{
if(i == num.size()-1 || num[i] > num[i+1])
{
cout << "delete" << num[i] << endl;
num.erase(num.begin()+i);
break;
}
}
}
cout << num << endl;
}
会输出所有被消除的数字和最终结果。
要这么删是逻辑思考，因为要得到最小数字就肯定是要按照升序排列（因为越靠前的数字的位数越大，要使整体数字小，这个位数上的数就一定要小。），如果不是升序排列，就要把刚开始降序的那个数给删除掉（也是越靠前越优先删除，因为位数大的关系），这样后面那个比较小的数就会来补充这个位数，这样就使数字变小了。
所以按着这个方法删肯定能得到最小数。
你在做的是一个多位数的问题吧
就是这样：
例如：
N = 123764
s = 2