SGU 296.Sasha vs. Kate（贪心）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：

给出长度为n(<=1000)的一个数。输出删掉k个数字后的最大值。

Solution：

简单贪心。

s[i]代表数字s的第i位.

从前往后第一个满足s[i]>s[i-1]的位置,最优一定是删除s[i-1]的.累计次数t.

同时对新得到的数同样处理,这里可以只用一个循环.如果用c++ string的话更加方便.

一直处理到t==k，或者没有满足条件的位置。

如果最后删除的次数t<k，只要从最后删掉k-t个数字。

时间复杂度O(n)

#include <iostream>

#include <string>

using namespace std;

string s;

int k,t;

int main()

{

    cin>>s>>k;

    for(int i=;i<s.size()&&t<k;++i){

        while(s[i]>s[i-]){

            s.erase(s.begin()+i-);

            if(++t==k) break;

            if(--i==) break;

        }

    }

    while(t<k){

        s.erase(s.end()-);

        ++t;

    }

    cout<<s<<endl;

}