当前位置:网站首页>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 AD in the library of library file suffix. Intlib. Schlib. Pcblib difference
- Introduction and use of BeautifulSoup4
- SIGINT,SIGKILL,SIGTERM信号区别,各类信号总结
- 买口罩(0-1背包)
- Explain the wait() function and waitpid() function in C language in detail
- vlucas/phpdotenv phpdotenv获取变量内容偶尔出现返回false
- 找不到和chrome浏览器版本不同的chromedriver的解决方法
- 长沙学院2022暑假训练赛(一)六级阅读
- The singleton pattern
- 力扣 636. 函数的独占时间
猜你喜欢
随机推荐
Output method of list string print(*a) print(““.join(str(c) for c in a) )
更改Jupyter Notebook默认打开目录
The solution that does not work and does not take effect after VScode installs ESlint
shardingsphere data sharding configuration item description and example
VS2019 common shortcut keys
SSL证书最长有效期13个月,还有必要一次申请多年吗?
eyb:Redis学习(2)
浅识微服务架构
Introduction and use of BeautifulSoup4
2022.8.8DAY628
Use of PlantUML plugin in idea
默默重新开始,第一页也是新的一页
Simple Factory Pattern
【烂笔头】各厂商手机手动抓log
字节也开始缩招了...
leetcode 之 零移位
APP product source data interface (taobao, jingdong/spelling/suning/trill platform details a lot data analysis interface) code and docking tutorial
分布式事务的应用场景
Simple to use Lambda expressions
6 states of a thread