摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Sasha vs. Kate ★☆☆☆☆ 答案正确 100 2015-2-19 21:08:48 3

(AC 1212)

题意

给一个数,求去掉k位后的最大值。

题解

  • 设该数n位,由题意显然是要使得答案的最高位尽量大,即取原数第1位到n-(n-k)+2位(保证后面位数够)之间的最大值,而之后每一位都取上一位位置到n-(n-k)+i+1位的最大值即可。区间最值可以用线段树处理。
  • 另一种可行的弹性策略是:每次从最高位遇到非递减的字符则删除(如果整个序列都是递减的,则删除最后一个数),直到够为止。如,19192,遇到连续上升的19则删除一个1,贪心正确性待证明[1][2]

代码

296.cpp代码已折叠
展开折叠内容
#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;
}

参考资料和拓展阅读

  1. http://blog.csdn.net/yzbyzz/article/details/9393889
  2. http://www.cppblog.com/willing/archive/2010/05/07/114778.html

著作权声明[编辑]

关于[编辑]