hdu3183 rmq求区间最值的下标
2024-08-22 16:28:38
两个月前做的题,以后可以看看,是rmq关于求区间最值的下标
/*
hdu3183
终点
给一个整数,可以删除m位,留下的数字形成一个新的整数
rmq
取n-m个数,使形成的数最小
*/
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define MAXN 1010
using namespace std;
int dp[MAXN][];
int a[MAXN];
void makeRMQ(int n,int b[]){//在i到1<<j区间内的最小值的下标
for(int i=;i<n;i++)
dp[i][]=i;//区间长度等于0时
for(int j=;(<<j)-<n;j++)
for(int i=;i+(<<j)-<n;i++)
if(b[dp[i][j-]]<=b[dp[i+(<<j-)][j-]])
//这里一定要加等号,就是相等的时候取下标小的
dp[i][j]=dp[i][j-];
else
dp[i][j]=dp[i+(<<j-)][j-];
}
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-(<<k)+][k]])
return dp[s][k];
else
return dp[v-(<<k)+][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=;i<n;i++)
a[i]=str[i]-'';
makeRMQ(n,a);
int t=;
int temp=;//temp最后=n-m
//找n-m个数,每次从[t,i]中找到最小的
for(int i=m;i<n;i++){
t=rmqIndex(t,i,a);
ans[temp++]=a[t++];
}
t=;
while(t<temp&&ans[t]==)
t++;//=滤掉高位的0!
if(t>=temp)
printf("0\n");
else{
for(int i=t;i<temp;i++)
printf("%d",ans[i]);
printf("\n");
}
}
return ;
}
最新文章
- 绘制图形与3D增强技巧(一)----点图元
- linux进程控制命令
- .NET 内存管理—CLR的工作
- andeoid学习笔记七
- MinGW安装和使用总结
- mysql 时间字段的函数 timestamp
- arcgis数据文件使用
- ANTS Performance Profiler 破解使用
- 手动安装英特尔&#174; 凌动™ Android* x86 模拟器映像
- new TimerTask(robot)(转)
- 201521123092《Java程序设计》第七周学习总结
- 灵感手环第一步——0.96寸OLED显示实验
- alpha-咸鱼冲刺day7
- linux iio子系统
- centos7图形界面安装
- Windows:添加、删除和修改静态路由
- [转]TA-Lib 安装
- C#编程的最佳工具
- 【URLOS应用开发基础】10分钟制作一个nginx静态网站环境应用
- Daily Scrum - 11/26