2014
03-06

# A Magic Lamp

Kiki likes traveling. One day she finds a magic lamp, unfortunately the genie in the lamp is not so kind. Kiki must answer a question, and then the genie will realize one of her dreams.
The question is: give you an integer, you are allowed to delete exactly m digits. The left digits will form a new integer. You should make it minimum.
You are not allowed to change the order of the digits. Now can you help Kiki to realize her dream?

There are several test cases.
Each test case will contain an integer you are given (which may at most contains 1000 digits.) and the integer m (if the integer contains n digits, m will not bigger then n). The given integer will not contain leading zero.

There are several test cases.
Each test case will contain an integer you are given (which may at most contains 1000 digits.) and the integer m (if the integer contains n digits, m will not bigger then n). The given integer will not contain leading zero.

178543 4
1000001 1
100001 2
12345 2
54321 2

13
1
0
123
321

http://acm.hdu.edu.cn/showproblem.php?pid=3183

RMQ算法：(ST算法，复杂度O(nlogn))
RMQ是区间最值查询，对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#define ll __int64
using namespace std;
#define N 1005
int num[N];//区间数值
int f[N][20];//f[i,j]表示从第i个数起连续2^j个数中的最小值,所以第二维大小应至少log(N)/log(2)
void initRMQ(int n)//初始化RMQ (nlogn)
{
for(int i=1;i<=n;i++)
{f[i][0]=num[i];}
for(int j=1;j<=log(n)/log(2);j++)
for(int i=1;i<=n+1-(1<<j);i++)
{f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);}
}
int RMQ(int i,int j)//查询RMQ
{
int k=log(j-i+1)/log(2);
return min(f[i][k],f[j-(1<<k)+1][k]);
}
int find(int from,int to,int x)//num[from,to]区间找最左边的值x
{
for(int i=from;i<=to;i++)
{
if(num[i]==x)
{return i;}
}
}
int main()
{
int i,j,k;
int n,m,t;
char ch[N];
while(scanf("%s%d",ch,&m)!=EOF)
{
for(i=0;i<strlen(ch);i++)
{num[i+1]=ch[i]-'0';}
if(m==strlen(ch))
{
printf("0\n");
continue;
}
initRMQ(strlen(ch));
queue<int>Q;
int from=1,to=m+1;
for(i=1;i<=strlen(ch)-m;i++)
{
int now=RMQ(from,to);
Q.push(now);
int index=find(from,to,now);
from=index+1;
to=from+m-(index-i);
}
int judge=0;
while(!Q.empty())
{
int now=Q.front();
Q.pop();
if(now==0)
{
if(judge==1)
{printf("0");}
}
else
{
printf("%d",now);
judge=1;
}
}
if(judge==0)
{printf("0");}
printf("\n");
}
}
/*
input:
178543 4
1000001 1
100001 2
12345 2
54321 2
output:
13
1
0
123
321
*/

http://dongxicheng.org/structure/lca-rmq/

1. 每个人有自己的业力，人类在进化这是不可阻挡的。转基因垃圾食品和肉食就是用来阻止人体进化的。未来只有高震动频率高能量的人才能适应，低频率者会被淘汰是宇宙的自然规律。

2. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.