题意：删去m个数，使剩下的数组成的数最小
题解 ：贪心 ， RMQ
RMQ解法，建st表找，用rmq找最小值的下标，注意点 ，因为最小值是区间最右最小值，所以应该改成 <= 而不是<
minpos[i][j] = b[minpos[i][j - 1]] <= b[minpos[i + (1 << (j - 1))][j - 1]] ? minpos[i][j - 1] : minpos[i + (1 << (j - 1))][j - 1];
且rmq查询也要同步
#include<iostream> #include<cstdio> #include<string> #include<cmath> #include<cstring> using namespace std; #define MAXN 20000 +9 #define MAXE 22 int h[MAXN],minpos[MAXN][MAXE]; int F_Min[MAXN][MAXE]; int N,Q; int L,R; // void RMQ_ST(){ // for(int i=1;i<=N;i++){ // mmax[i][0]=h[i]; // } // int end_j=log(N+0.0)/log(2.0); // int end_i; // for(int j=1;j<=end_j;j++){ // end_i=N+1-(1<<j); // for(int i=1;i<=end_i;i++){ // //mmax[i][j]=max(mmax[i][j-1],mmax[i+(1<<(j-1))][j-1]); // mmin[i][j]=min(mmin[i][j-1],mmin[i+(1<<(j-1))][j-1]); // } // } // } // int QueryMin(int L,int R){ // int k=log(R-L+1.0)/log(2.0); // return min(mmin[L][k],mmin[R-(1<<k)+1][k]); // } void RMQ_pos_init(int n, int b[]){ int i, j; for (i = 1; i <= n; i++) { // maxpos[i][0] = i; minpos[i][0] = i; } for (j = 1; (1 << j) <= n; j++) for (i = 1; i + (1 << j) - 1 <= n; i++){ minpos[i][j] = b[minpos[i][j - 1]] <= b[minpos[i + (1 << (j - 1))][j - 1]] ? minpos[i][j - 1] : minpos[i + (1 << (j - 1))][j - 1]; //maxpos[i][j] = b[maxpos[i][j - 1]] > b[maxpos[i + (1 << (j - 1))][j - 1]] ? maxpos[i][j - 1] : maxpos[i + (1 << (j - 1))][j - 1]; } } int RMQ_pos_min(int s, int v, int b[]){ int k = (int)(log((v - s + 1)*1.0) / log(2.0)); return b[minpos[s][k]] <= b[minpos[v - (1 << k) + 1][k]] ? minpos[s][k] : minpos[v - (1 << k) + 1][k]; } char str[1000+ 9]; int ans[1000 + 9]; int main(int argc, char const *argv[]) { int n; while(~scanf("%s %d",&str,&n)){ int len = strlen(str); int l = 1, r = n + 1; int m = len - n ; int sum = 0; for(int i = 0; i < len; i ++){ h[i + 1] = str[i] - '0'; } // for(int i = 1;i ) RMQ_pos_init(len,h); while(m--){ int i = l ; int size = l ; // for(;i <= r;i++){ // if((str[i] - '0') < (str[size] - '0')) size = i; // } //cout << l << " " << r << endl; size = RMQ_pos_min(l,r,h); //cout << size << endl; ans[sum++] = h[size]; l = size + 1; r++; } int i = 0; while(ans[i] == 0 && i < sum) i++; if(i == sum) printf("0"); else // for(auto au : ans){ // printf("%d",ans ); // } for(;i < sum; i++) printf("%d",ans[i]); printf(" "); } return 0; }
贪心解法
删除m个数字，相当于在里面从左往右取n-m个数字；所得数最小，也就是每次取得数字尽量小。那么，取得的第一个数字一定在区间[0,m]内，为什么呢？因为除了第一个数之外还要取n-m-1个数字，所以区间右边界最大只能是m，每次在区间里找最小的那个数(尽量靠左)；依次类推，假设第一个数字取得的下标是index1，那么，第二个数字一定是在[index1+1,m+1]内取得；依次类推下去，右边界每次加1。当选取到了n-m个数字之后，也就找到了答案了~
#include<iostream> #include<cstdio> #include<string> #include<cmath> #include<cstring> using namespace std; #define MAXN 200000 +9 #define MAXE 22 int h[MAXN],mmax[MAXN][MAXE]; int N,Q; int L,R; void RMQ_ST(){ for(int i=1;i<=N;i++){ mmax[i][0]=h[i]; } int end_j=log(N+0.0)/log(2.0); int end_i; for(int j=1;j<=end_j;j++){ end_i=N+1-(1<<j); for(int i=1;i<=end_i;i++){ mmax[i][j]=max(mmax[i][j-1],mmax[i+(1<<(j-1))][j-1]); // mmin[i][j]=min(mmin[i][j-1],mmin[i+(1<<(j-1))][j-1]); } } } int QueryMax(int L,int R){ int k=log(R-L+1.0)/log(2.0); return max(mmax[L][k],mmax[R-(1<<k)+1][k]); } char str[1000+ 9]; int ans[1000 + 9]; int main(int argc, char const *argv[]) { int n; while(~scanf("%s %d",&str,&n)){ int len = strlen(str); int l = 0, r = n; int m = len - n; int sum = 0; while(m--){ int i = l; int size = l; for(;i <= r;i++){ if((str[i] - '0') < (str[size] - '0')) size = i; } ans[sum++] = str[size] - '0'; l = size + 1; r++; } int i = 0; while(ans[i] == 0 && i < sum) i++; if(i == sum) printf("0"); else // for(auto au : ans){ // printf("%d",ans ); // } for(;i < sum; i++) printf("%d",ans[i]); printf(" "); } return 0; }