（以“分类:贪心 ==摘要== {{信息题|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 121...”为内容创建页面） |
小 （<references/>） |
||
| 第84行： | 第84行： | ||
</pre> | </pre> | ||
|sgu296}} | |sgu296}} | ||
| + | ==参考资料和拓展阅读== | ||
| + | <references/> | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| Sasha vs. Kate | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-19 21:08:48 | 3 |
（AC 1212）
给一个数，求去掉k位后的最大值。
| 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;
}
|
CloudLunar