题目链接:https://codeforces.ml/problemset/problem/1765/N
删数问题,存在0元素,且首位不能为0,求删除k个数后的最小值为多少。
思路:删数问题一般跑不了贪心。因为我们总应该要贪婪的选择删除前面的数,将靠前的大数消灭掉。
我们需要解决的是冲突问题 存在 90000123 900123 ,如果删除三个数,那么两个数的删除的手段是不同的。
考虑使用邻接表来存储每个数字所在的位置。我们需要保留n-k个数。第一个需要保留的一定不能是0,所以我们从1开始考虑1的位置是否符合,然后找到符合的,对于之后的任意删除这个位置之前的所有元素。继续判断即可。同时不断的更新保留后的最后位置,和k的值(这里比较恶心,需要处理一些边界问题)。
code:
void solve() { string s; cin>>s; int k; cin>>k; int n = s.size(); vector<vector<int>> ve(10); for(int i=0;i<n;i++)//存储位置 ve[s[i]-'0'].push_back(i); for(int i=0;i<10;i++)//对位置进行反向 reverse(ve[i].begin(),ve[i].end()); string ans; int lst = 0,len = n-k; for(int i=0;i<len;i++){//我们想要len个数 for(int d = (i==0);d<=9;d++){//然后来看我们需要保留的数,如果是首位,那么我们不必考虑0 while(!ve[d].empty()&&ve[d].back()<lst)//这个数之前的我们不能取了,因为我们需要保证有序 ve[d].pop_back(); if(!ve[d].empty()&&ve[d].back()-lst<=k){//这时来看一下,我们取的满不满足范围 ans+=d+'0'; k-=ve[d].back()-lst;//里面的数都删了 lst = ve[d].back()+1; break; } } } cout<<ans<<endl; }
挑战OL网页游戏一条龙www.45ur.com776356990@qq.com绝对女神传说OL刀剑服务端出售
Reply天龙一条龙奇迹Mu一条龙魔兽一条龙魔域一条龙墨香一条龙
天堂2一条龙传奇3一条龙英雄王座一条龙千年一条龙征途一条龙
新魔界一条龙骑士一条龙烈焰一条龙破天一条龙决战一条龙
美丽世界一条龙乱勇OL一条龙倚天2一条龙完美世界一条龙征服一条龙
天堂一条龙传世一条龙真封神一条龙劲舞团一条龙天上碑一条龙
永恒之塔一条龙仙境RO一条龙诛仙一条龙神泣一条龙石器一条龙
冒险岛一条龙惊天动地一条龙热血江湖一条龙问道一条龙密传一条龙
火线任务(Heat Project)一条龙飞飞OL一条龙洛汗一条龙天之炼狱一条龙
丝路传说一条龙大话西游一条龙蜀门一条龙机战一条龙剑侠情缘一条龙
绝对女神一条龙传说OL一条龙刀剑一条龙弹弹堂一条龙科洛斯一条龙
魔力宝贝一条龙武林外传一条龙网页游戏一条龙页游一条龙希望OL一条龙
成吉思汗一条龙剑侠世界一条龙全民奇迹一条龙挑战OL一条龙
红月一条龙十二之天(江湖OL)一条龙倚天一条龙dnf一条龙
————————————————————————————————
很多第一次想开F的客户,基本都是发一个版本给我们,问我们有没有这样的版本,首先我们申明,版本都是要进行修改的,因为每个GM都有自己的想法和设计,不可能有一模一样的版本,只能进行修改和制作后才能做到相同.关于开服,我们可以模仿做任何版本,这个是肯定不可争议的.主营业务:手游端游页游服务端版本一条龙开服+服务器租用+网站建设修改+广告宣传渠道,本团队正规公司化运营,拥有自己的专业技术团队,合理的价格。专业诚信为您量身定做独家专业的网络游戏,打造属于自己的网络私F,圆您一个GM梦想.
看不明白QAQ 能不能說再清楚一點 "我们从1开始考虑1的位置是否符合,然后找到符合的" 符合什麼條件?
Reply