当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
随机推荐
物理层课后作业
详解C语言中的wait()函数和waitpid()函数
排序第四节——归并排序(附有自己的视频讲解)
eyb:Redis学习(2)
Error jinja2.exceptions.UndefinedError: 'form' is undefined
imageio读取.exr报错 ValueError: Could not find a backend to open `xxx.exr‘ with iomode `r`
C language implements sequential stack and chain queue
神经网络优化器
TCP段重组PDU
Introduction and use of BeautifulSoup4
Use of PlantUML plugin in idea
mysql summary
什么是分布式事务
MVN 中配置flyway mysq
字节也开始缩招了...
The division principle summary within the collection
longest substring without repeating characters
Common Oracle Commands
codeforces Valera and Elections (这思维题是做不明白了)
找出数组中不重复的值php