keks（删数问题）

本文主要是介绍keks（删数问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

4509: keks

时间限制: 1 Sec   内存限制: 128 MB
提交: 19   解决: 4
[ 提交][ 状态][ 讨论版]

题目描述

输入

输出

样例输入

4 2

1924

样例输出

94

蛮经典的题目，删除数字，思路是因为大数越靠前越好，所以要从前往后删，然后通过删数来保证维持一个递减数列，删数用vis[]数组来表示，每次用head往后找一位，然后检查前面是否有比n[head]要小的数字，若有，就删除他。有一个小技巧，怎么回到上一个没有被删除的数字，是while（）循环每次减1到没有标记vis[]的地方。这道题快debug疯了，简直和ac代码写的一模一样了，但就是ac不了，老是第五个样例卡时间，算了，不找了，算法基本上都确定没问题了就懒得改了。

我的T代码：

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main()
{string n;int num,s,head,tail;int vis[102]={0};scanf("%d%d",&num,&s);getchar();cin>>n;head=1;tail=0;while(s&&head<num){while(n[tail]<n[head]&&tail>=0&&s){s--;vis[tail]=1;while(vis[tail]&&tail>=0)tail--;}tail=head;head++;}head=num-1;while(s&&head>=0){if(!vis[head]){vis[head]=1;s--;}head--;}for(int i=0;i<num;i++)if(!vis[i])printf("%c",n[i]);puts("");return 0;
}

抄来的ac代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#define ll long long
#define mset(a,x) memset(a,x,sizeof(a))using namespace std;
const double PI=acos(-1);
const int inf=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=5e5+5;
const int mod=1e9+7;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
char map[maxn];
int visit[maxn];int main()
{int n,k,i,j;while(cin>>n>>k){getchar();cin>>map;mset(visit,1);int l=0,r=1;while(r<n&&k){while(l>=0&&k&&map[l]<map[r]){k--;visit[l]=0;while(l>=0&&!visit[l])l--;}l=r;r++;}r=n-1;while(k&&r>=0){if(visit[r]){visit[r]=0;k--;}r--;}for(i=0;i<n;i++){if(visit[i])cout<<map[i];}cout<<endl;}return 0;
}

这篇关于keks（删数问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---