文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。
继续贪心,POJ上找不到,Vijos上倒是有,不过它现在挂了...
键盘输入一个高精度的正整数N(<=240位),去掉任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S,寻找一种方案,使得剩下的数最小。
Simple Input
178543
4
Simple Output
13
Slyar:考虑只删一个数的情况,最优解是删除出现的第一个左边>右边的数,因为删除之后高位减小,很容易想...那全局最优解也就是这个了,因为删除S个数字就相当于执行了S次删除一个数,因为留下的数总是当前最优解...贪心吧,代码还没验证,等OJ好了交一下看看,应该没问题...
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 |
#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++版