当前位置:网站首页>HDU - 3183 A Magic Lamp 线段树
HDU - 3183 A Magic Lamp 线段树
2022-08-09 07:01:00 【swust_fang】
题目链接
题意:数字字符串删除k个值后的数字最小不算前导0
思路:其实就是最小字典序,那么我们肯定一位一位的确定最小的值,那么对于i位,其实找i+1~i+k位中最小的数有没有比当前位置的数小,如果有的话就是把中间的都删掉。所以其实就是求某一位i右边i+1~i+1+k中最小值的最小下标,我们可以用线段树来维护。哈哈哈~问了问学长,学长骂我智障(hh
其实就是线段树维护个node,重载一下就行~
我看题解居然还有n方的过的,太可惜了
AC代码:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
#define li __int128
//void print(li x) {if(x>9) print(x/10);putchar(x%10+48);}
const int dir[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};
typedef long long ll;
typedef unsigned long long ull;
const ll inFF = 9223372036854775807;
const int maxn=1e5+5;
const ll mod=1e9+7;
using namespace std;
int a[maxn];
char s[maxn];
struct node
{
int val,pos;
bool friend operator<(node s,node e)
{
if(s.val==e.val) return s.pos<e.pos;
return s.val<e.val;
}
}tree[maxn<<1];
int n,k,vis[maxn];
void pushup(int i)
{
tree[i]=(tree[lson]<tree[rson])?tree[lson]:tree[rson];
}
void build(int i,int l,int r)
{
if(l==r)
{
tree[i]=node{a[l],l};
return;
}
int mid=half;
build(Lson);
build(Rson);
pushup(i);
}
node query(int i,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r) return tree[i];
int mid=half;
if(qr<=mid) return query(Lson,ql,qr);
else if(ql>mid) return query(Rson,ql,qr);
else
{
node s=query(Lson,ql,mid);
node e=query(Rson,mid+1,qr);
if(s<e) return s;
else return e;
}
}
int main()
{
while(scanf("%s",s+1)!=EOF)
{
n=strlen(s+1);
for(int i=1;i<=n;i++) a[i]=s[i]-'0',vis[i]=0;
cin>>k;
build(1,1,n);
int c=k;
for(int i=1;i<=n&&c>0;i++)
{
if(c>=n-i+1)
{
for(int j=i;j<=n;j++)vis[j]=1;
break;
}
if(a[i]==0)
{
vis[i]=0;
continue;
}
node now=query(1,1,n,i+1,min(i+c,n));
if(now.val<a[i])
{
vis[now.pos]=0;
for(int j=i;j<now.pos;j++) vis[j]=1;
c-=now.pos-i;
i=now.pos;
}
else vis[i]=0;
}
int num=0,fg=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
if(a[i]==0&&fg==0) continue;
printf("%d",a[i]),num++,fg=1;
}
}
if(num==0) puts("0");
else printf("\n");
}
return 0;
}
边栏推荐
- The water problem of leetcode
- install flask
- 日期处理,字符串日期格式转换
- Example of using the cut command
- SAP ALV 数据导出被截断的bug
- db.sqlite3 has no "as Data Source" workaround
- failed (13: Permission denied) while connecting to upstream
- 错误:为 repo ‘oracle_linux_repo‘ 下载元数据失败 : Cannot download repomd.xml: Cannot download repodata/repomd.
- makefile记录
- 网络学习总结
猜你喜欢
DSP+ARM+FPGA高速PCIE/千兆网口信号仿真介绍
基于布朗运动的文本生成方法-LANGUAGE MODELING VIA STOCHASTIC PROCESSES
Altium designer软件常用最全封装库,包含原理图库、PCB库和3D模型库
Inception V3 闭眼检测
Mysql实操
ByteDance Written Exam 2020 (Douyin E-commerce)
stm32定时器之简单封装
SAP ALV 数据导出被截断的bug
2022-08-08: Given an array arr, it represents the height of the missiles that will appear in order from morning to night.When the cannon shoots missiles, once the cannon is set to shoot at a certain h
6 states of a thread
随机推荐
Zero shift of leetcode
金九银十即将到来,求职套路多,面试指南我来分享~
Quectel EC20 4G module dial related
搭载开源鸿蒙系统的嵌入式XM-RK3568工业互联方案
P6 ali machine test of 2020 Fibonacci number
shardingsphere data sharding configuration item description and example
XxlJobConfig distributed timer task management XxlJob configuration class, replace
Common Oracle Commands
高项 01 信息化与信息系统
MUI无法滚动?完美解决
Simple Factory Pattern
分布式事务的应用场景
【转载】Deep Learning(深度学习)学习笔记整理
01 自然语言处理NLP介绍
cut命令的使用实例
jvm线程状态
Explain the wait() function and waitpid() function in C language in detail
Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
【烂笔头】各厂商手机手动抓log
Built-in macros in C language (define log macros)