删数问题 c++版

文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

继续贪心，POJ上找不到，Vijos上倒是有，不过它现在挂了...

键盘输入一个高精度的正整数N(<=240位)，去掉任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案，使得剩下的数最小。

Simple Input
178543
4

Simple Output
13

Slyar:考虑只删一个数的情况，最优解是删除出现的第一个左边>右边的数，因为删除之后高位减小，很容易想...那全局最优解也就是这个了，因为删除S个数字就相当于执行了S次删除一个数，因为留下的数总是当前最优解...贪心吧，代码还没验证，等OJ好了交一下看看，应该没问题...

#include <iostream>
#include <string>

using namespace std;

string greedy(string& str, int n)
{
	bool del;
	for (int i = n; i > 0; i--)
	{
		del = false;
		// 每次删除第一个比下一个数字大的数
		for (string::iterator it = str.begin(); it != str.end()-1; it++)
		{
			if (*it > *(it+1))
			{
				str.erase(it);
				del = true;
				break;
			}
		}
		//如果所有数字递增，则删除最后几个数字直接返回
		if (!del)
		{
			str.erase(str.end()-i, str.end());
			break;
		}
	}
	return str;
}

int main()
{
	int n;
	string str;
	cin >> str;
	cin >> n;

	cout << greedy(str, n) << endl;

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

string greedy(string& str, int n)

{

bool del;

for (int i = n; i > 0; i--)

{

del = false;

// 每次删除第一个比下一个数字大的数

for (string::iterator it = str.begin(); it != str.end()-1; it++)

{

if (*it > *(it+1))

{

str.erase(it);

del = true;

break;

}

//如果所有数字递增，则删除最后几个数字直接返回

if (!del)

{

str.erase(str.end()-i, str.end());

break;

}

return str;

}

int main()

{

int n;

string str;

cin >> str;

cin >> n;

cout << greedy(str, n) << endl;

return 0;

}

转载请注明：Slyar Home » 删数问题 c++版

与本文相关的文章

Hi，您需要填写昵称和邮箱！