首页 > 代码库 > hdu 3183 A Magic Lamp(给一个n位的数,从中删去m个数字,使得剩下的数字组成的数最小(顺序不能变),然后输出)
hdu 3183 A Magic Lamp(给一个n位的数,从中删去m个数字,使得剩下的数字组成的数最小(顺序不能变),然后输出)
1.题目大意是,给你一个1000位的数,要你删掉m个为,求结果最小数。
思路:在n个位里面删除m个位。也就是找出n-m个位组成最小数
所以在区间 [0, m]里面找最小的数。相应的下标标号i
接着找区间 [i+1,m++]里面的最小数。对于下标为ii
接着找区间 [ii+1,m++]里面的最小数……
这样就会找n-m个数了。区间这样安排的目的是为了保证取出来的数的顺序。
2代码:
#include<cstdio> #include<cstring> #include<cmath> #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; char s[10005]; int a[10005]; int an[10005]; int ST[10005][20]; int n,m; void make_ST()//记录的是最小值的下标 { for(int j=1; (1<<j)<=n; j++) { for(int i=1; (i+(1<<j)-1)<=n; i++) { if(a[ST[i][j-1]]<=a[ST[i+(1<<(j-1))][j-1]])//得取等号,使得两个数相等的时候取下标小的 ST[i][j]=ST[i][j-1]; else ST[i][j]=ST[i+(1<<(j-1))][j-1]; } } } int Query(int l,int r) { int k=floor(log2(r-l+1)); int ans; if(a[ST[l][k]]<=a[ST[r-(1<<k)+1][k]]) ans=ST[l][k]; else ans=ST[r-(1<<k)+1][k]; return ans; } int main() { while(scanf("%s%d",s,&m)==2) { n=strlen(s); for(int i=0; i<n; i++) { a[i+1]=(s[i]-'0'); ST[i+1][0]=i+1; } make_ST(); int t=1; int temp=1; for(int i=m+1; i<=n; i++) //找n-m个数,每次从[t,i]中找最小的 { t=Query(t,i); an[temp++]=a[t++]; } t=1; while(t<temp&&an[t]==0) t++; if(t>=temp) printf("0\n"); else { for(int i=t; i<temp; i++) printf("%d",an[i]); printf("\n"); } } return 0; }
hdu 3183 A Magic Lamp(给一个n位的数,从中删去m个数字,使得剩下的数字组成的数最小(顺序不能变),然后输出)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。