两个月前做的题，以后可以看看，是rmq关于求区间最值的下标
/* hdu3183 终点 给一个整数，可以删除m位，留下的数字形成一个新的整数 rmq 取n-m个数，使形成的数最小 */ #include<iostream> #include<cstring> #include<cmath> #include<cstdio> #define MAXN 1010 using namespace std; int dp[MAXN][20]; int a[MAXN]; void makeRMQ(int n,int b[]){//在i到1<<j区间内的最小值的下标 for(int i=0;i<n;i++) dp[i][0]=i;//区间长度等于0时 for(int j=1;(1<<j)-1<n;j++) for(int i=0;i+(1<<j)-1<n;i++) if(b[dp[i][j-1]]<=b[dp[i+(1<<j-1)][j-1]]) //这里一定要加等号，就是相等的时候取下标小的 dp[i][j]=dp[i][j-1]; else dp[i][j]=dp[i+(1<<j-1)][j-1]; } int rmqIndex(int s,int v,int b[]){//在区间s->v之间找区间最小值， //加等号，取小标小的 //1<<k+1的长度必须覆盖[s,v] int k=(int)(log(v-s+1.0)/log(2.0));//k就是那个区间[s,v]长度的log2 if (b[dp[s][k]]<=b[dp[v-(1<<k)+1][k]]) return dp[s][k]; else return dp[v-(1<<k)+1][k]; } char str[MAXN]; int ans[MAXN]; int main(){ int m; while(scanf("%s%d",&str,&m)!=EOF){ int n=strlen(str); for(int i=0;i<n;i++) a[i]=str[i]-'0'; makeRMQ(n,a); int t=0; int temp=0;//temp最后=n-m //找n-m个数，每次从[t,i]中找到最小的 for(int i=m;i<n;i++){ t=rmqIndex(t,i,a); ans[temp++]=a[t++]; } t=0; while(t<temp&&ans[t]==0) t++;//=滤掉高位的0！ if(t>=temp) printf("0\n"); else{ for(int i=t;i<temp;i++) printf("%d",ans[i]); printf("\n"); } } return 0; }
转载于:https://www.cnblogs.com/zsben991126/p/10056850.html
相关资源：各显卡算力对照表！