RMQ hdu 3183 A Magic Lamp
RMQ hdu 3183 A Magic Lamp//hdu 3183 A Magic Lamp
//RMQ
//用RMQ求剩下的n-m个数,第一个数肯定在第一个数和第m+1 个数之间的最小的那个数，
//包括第一和m+1，第二个数肯定在上一次求的数到第m+2 个数之间，依次类推
//注意:预处理log时，记得最大下标是所给数的长度，不是2的几次方，
//下标就是多少。求最小数时，若有多个和最小值相等的数则去最左的那个，
//要不然求下一个最小数时会忽略这些数
#include <stdio.h>
#include <string.h>
//#include <math.h>
#include <algorithm>
using namespace std;
#define comein freopen("in.txt", "r", stdin);
#define comeout freopen("out.txt", "w", stdout);
#define N 1005
#define INF 1<<30
#define eps 1e-5
char num;
int dp_min, pos;
int lo_2;
void RMQ(int len)
{
for(int i = 1; i <= len; ++i)
dp_min = i;
int index = lo_2;
for(int i = 1; i <= index; ++i)
{
for(int j = 1; j + (1<<i) - 1 <= len; ++j)
{
if(num] <= num])
dp_min = dp_min;
else
dp_min = dp_min;
}
}
}
int get_min_pos(int from, int to)
{
int index = lo_2;
//若有多个和最小值相等的数则去最左的那个，所以这里要取等
if(num] <= num])
return dp_min;
return dp_min;
}
int main()
{
lo_2 = -1;
for(int i = 1; i < N; ++i) //求2为底的对数
lo_2 = i&(i-1) ? lo_2 : lo_2 + 1;
while(scanf("%s", &num) != EOF)
{
int del_n, len = strlen(&num);
RMQ(len);
scanf("%d", &del_n);
int left = len - del_n, from = 1, to;
to = del_n + 1;
while(left)
{
pos = get_min_pos(from, to);
from = pos + 1;
to++;
left--;
}
left = len - del_n;
sort(pos, pos + left);
int i = 0;
while(num] == '0' && i < left)
i++;
if(i == left)
{
puts("0");
continue;
}
for(; i < left; ++i)
putchar(num[ pos ]);
puts("");
}
return 0;
}
页:
[1]