注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 3183 A Magic Lamp  

2013-08-21 17:47:27|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=3183
给出一个最大长1000的整数n,还有一个整数m,问去掉n中m个数字,使得最后剩下的数字最小,要求顺序不变。
RMQ的应用。只不过存的是数组的下标。参见:http://blog.csdn.net/azheng51714/article/details/8555710
去掉m个数字,使得最后数字最小,相当于选n-m个数字,使得组成的数字最小。

先在区间 [0, m]里面找最小的数,对应的下标标号i;接着找区间 [i+1,m++]里面的最小数,对于下标为ii;接着找区间 [ii+1,m++]里面的最小数……这样就会找到n-m个数了。区间这样安排的目的是为了保证取出来的数的顺序。

/*
* pro.cpp
*
* Created on: 2013-08-21
* Author: fudq
*/
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=1010;
const int M=32010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

char s[N];
int n,tot,f[N],ans[N],rmq_n[N][32];

int check(int i,int j)
{
return f[i]<=f[j]?i:j;
}

void rmq_init(int arr[],int n)
{
int i,j;
for(i=1;i<=n;i++)
rmq_n[i][0]=i;
for(j=1;(1<<j)<=n;j++)
for(i=1;i+(1<<j)-1<=n;i++)
rmq_n[i][j]=check(rmq_n[i][j-1],rmq_n[i+(1<<(j-1))][j-1]);
}

int rmq(int a,int b)
{
int m=int(log(b-a+1.0)/log(2.0));
int x=check(rmq_n[a][m],rmq_n[b-(1<<m)+1][m]);
return x;
}

void solve()
{
int len=(int)strlen(s);
for(int i=0;i<len;i++)
f[i+1]=s[i]-'0';
rmq_init(f,len);

int lef,rig;
tot=0;lef=1;rig=n+1;
while(tot < len-n)
{
int t=rmq(lef,rig);
ans[tot++]=f[t];
lef=t+1;rig++;
}
int p=0;
while(ans[p] == 0 && p<tot)
p++;
if(p == tot)
printf("0");
for(int i=p;i<tot;i++)
printf("%d",ans[i]);
printf("\n");
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
while(scanf("%s %d",s,&n)!=EOF)
solve();
return 0;
}



  评论这张
 
阅读(87)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017