題目：A Magic Lamp

?

題意：

對(duì)于一個(gè)序列A[1...N]，一共N個(gè)數(shù)，除去M個(gè)數(shù)使剩下的數(shù)組成的整數(shù)最小。

也就是說(shuō)在A[1...N]中順次選取N-M個(gè)數(shù)，使值最小。

本題很有技巧性，一開(kāi)始我總是想不明白，后來(lái)在紙上畫(huà)了一下，大概明白了是怎么回事。

它主要是基于以下事實(shí)：

對(duì)于序列A[1...N]，選取N-M個(gè)數(shù)，使組成的值最小，而且順序不能交換，既然要選取N-M個(gè)，那么可以容易知道這N-M位數(shù)的第一位一定在數(shù)組A中的區(qū)間

[1，M+1]中出現(xiàn)，為什么是這樣呢？

我們可以這樣來(lái)模擬一下：假設(shè)A數(shù)組就只有6個(gè)數(shù)，分別是A[1]，A[2]，A[3]，A[4]，A[5]，A[6]，我們?nèi)サ?/span>M=2個(gè)數(shù)，使形成的值最小。

那么我們此時(shí)的N=6,M=2，N-M=4

則我們說(shuō)形成的4位數(shù)的第一位一定在區(qū)間[1，3]中出現(xiàn)，因?yàn)槿绻麉^(qū)間范圍再大點(diǎn)，比如[1，4]，這樣就不科學(xué)了，因?yàn)榈谝晃灰欢ú粫?huì)是A[4]，更不會(huì)是

A[5]，A[6]，我們假設(shè)可以是A[4]，那么后面只有A[5]，A[6]兩位數(shù)了，這樣的話最多只可能形成3位數(shù)，絕對(duì)不能形成N-M=4位了。

當(dāng)然到了這里，我們就可以這樣做了，第一位可以在區(qū)間[1，M+1]里面找，假設(shè)第一位在位置x，因?yàn)榈诙豢隙ㄔ诘谝晃坏暮竺?#xff0c;所以第二位一定存在于

區(qū)間[x+1，M+2]，為什么是M+2,因?yàn)榈谝晃灰呀?jīng)確定了，現(xiàn)在只需要確定N-M-1位了，所以區(qū)間就可以向后增加1，一直這樣循環(huán)下去，就可以找到了。

?

#include <stdio.h> #include <string.h> #include <math.h> #define N 1005int m,n; char a[N]; char num[N]; int f[N][N];int min(int i,int j) {return a[i]<=a[j] ? i:j; }void ST() {int i,j;for(i=0;i<n;i++)f[i][0]=i;for(j=1;j<=(int)(log((double)n)/log(2.0));j++){for(i=0;i+(1<<j)-1<n;i++)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);} }int query(int L,int R) {int x=(int)(log(double(R-L+1))/log(2.0));return min(f[L][x],f[R-(1<<x)+1][x]); }int main() {int i,j,L,R;while(~scanf("%s%d",a,&m)){int len=strlen(a);n=len;m=len-m;ST();i=j=0;while(m--){i=query(i,len-m-1);num[j++]=a[i++];}for(i=0;i<j;i++){if(num[i]!='0')break;}if(i==j){puts("0");continue;}while(i<j){printf("%c",num[i]);i++;}puts("");}return 0; }

?

超強(qiáng)干貨來(lái)襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的HDU3183(RMQ问题，ST算法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。