查看Sgu/296的源代码 ←Sgu/296

[[分类:贪心]]
==摘要==
{{信息题|Sasha vs. Kate|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}296|1|100|k=n-k|3|time=2015-2-19 21:08:48}}
（AC 1212）
==题意==
给一个数，求去掉k位后的最大值。
==题解==
*设该数n位，由题意显然是要使得答案的最高位尽量大，即取原数第1位到<small>n-(n-k)+2位(保证后面位数够）</small>之间的最大值，而之后每一位都取上一位位置到<small>n-(n-k)+i+1</small>位的最大值即可。区间最值可以用[[线段树]]处理。
*另一种可行的弹性策略是：每次从最高位遇到非递减的字符则删除（如果整个序列都是递减的，则删除最后一个数），直到够为止。如，19192，遇到连续上升的19则删除一个1，贪心正确性待证明<ref>http://blog.csdn.net/yzbyzz/article/details/9393889</ref><ref>http://www.cppblog.com/willing/archive/2010/05/07/114778.html</ref>。
==代码==
{{折叠|296.cpp代码已折叠
|<pre>
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#define si(n) scanf("%d",&n)
#define dsi(n) int n;si(n)
using namespace std;
string str;
class ch
{
    public:
    char p;
    int index;
    ch():p(0),index(0){};
    friend bool operator <(const ch&a,const ch&b){return a.p==b.p?a.index>b.index:a.p<b.p;}
};
template<size_t N>
class SegmentTree
{
    //模板：线段树//
public:
    ch tree[N];
    #define cm int m=(l+r)>>1
    #define lp p<<1
    #define rp p<<1|1
    #define lc lp,l,m
    #define rc rp,m+1,r
    #define stdp int p,int l,int r
    ch build(stdp)
    {
        if(l==r)
        {
            tree[p].p=str[l-1];
            tree[p].index=l;
            return tree[p];
        }
        cm;
        return tree[p]=max(build(lc),build(rc));
    }
    ch query(int L,int R,stdp)
    {
        if(L<=l&&r<=R) return tree[p];
        ch ret;
        ret.p=0;
        cm;
        if(L<=m)ret=max(query(L,R,lc),ret);
        if(R>m)ret=max(query(L,R,rc),ret);
        return ret;
    }
};
SegmentTree<20000> st;
int n;

int main()
{
    cin>>str;
    int n=str.size();
    st.build(1,1,n);
    dsi(k);
    k=n-k;//fixed//
    string a;
    int lastIndex=0;
    for(int i=0;i<k;++i)
    {
        ch ret=st.query(lastIndex+1,n-k+i+1,1,1,n);
        cout<<ret.p;
        lastIndex=ret.index;
    }
    cout<<a;
}

</pre>
|sgu296}}
==参考资料和拓展阅读==
<references/>