文档章节

CodeForces - 95B(搜索+贪心)

o
 osc_1ee7cxmx
发布于 2018/08/06 16:04
字数 734
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目链接:http://codeforces.com/problemset/problem/95/B

题意:给一个正整数n(1-100000位),求出不小于n的最小幸运。幸运数的概念是:由数量相等的4和7组成的数。

思路:

大体分三种情况:

1.n的位数len为奇数,最简单就是增加一位变成len+1偶数个,前一半为4,后一半为7

2.n的位数len为偶数,但找不到有len位数的幸运数比n大,那么就要增加两位len+2,前一半为4,后一半为7(可以和情况1放在一起)

3.n的位数len为偶数,可以找到幸运数。这种情况就要搜索找到最小的了。

因为数的位数过大,时间复杂度只能是O(n)或者O(nlogn)。

 

这里就要用到贪心的思路了,我们搜索遍历每一位,先将能变成4的变为4,在看变为7。

如果遍历的这位已经变大了,那么就不用考虑后面的数了,直接排。此时就是最小的

 

自己太弱了,看了大佬的代码,才知道还可以这样。只要考虑<=4和<=7的情况,>7的情况不用考虑了,因为要不数值太大,没有符合的幸运数,要不是前面已经变大了不用考虑。

我本来还有一个疑问的就是,4和7的个数不能均分怎么办比如7774。看了大佬代码才知道,开始搜索条件直接为dfs(int pos,int n4,int n7,int tag)(pos为搜索现在的位数,n4,n7为可以用的个数,tag标记已经变大了)

直接无视了这种情况,只要呢,n4,n7的可用个数不够,直接false了。

具体可以看代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
char s[100005];
char ans[100005];
int len;
bool dfs(int pos,int n4,int n7,bool tag)//pos为当前位置,n4,n7为可用的4,7个数,tag为标记是否变大 
{
    if(pos>=len)//搜索到最后,没有退出,那么就是该ans就是答案。这是判断n本身就是幸运数的情况 
        return true;
    if(tag)//已经变大 
    {
        for(int i=0;i<n4;i++)//后面接可用个数的4 
            ans[i+pos]='4';
        for(int i=0;i<n7;i++)//再接可用个数的e7 
            ans[i+pos+n4]='7';
        return true;
    }
    if(s[pos]<='4'&&n4)//先判断可变为4的 
    {
        if(dfs(pos+1,n4-1,n7,s[pos]<'4'))//<4在为变大,=4会继续搜索 
        {
            ans[pos]='4';
            return true;
        }
    }
    if(s[pos]<='7'&&n7)//在判断可变为7的 
    {
        if(dfs(pos+1,n4,n7-1,s[pos]<'7'))
        {
            ans[pos]='7';
            return true;
        }
    }
    return false;
}
int main()
{
    while(cin>>s)
    {
        len=strlen(s);
        if(len%2==1||!dfs(0,len/2,len/2,0))
        {
            len+=1+(len%2==0);//len为奇数+1,偶数搜索不到+2 
            for(int i=0;i<len/2;i++)
                ans[i]='4';
            for(int i=len/2;i<len;i++)
                ans[i]='7'; 
        }
        ans[len]='\0';
        cout<<ans<<endl;
    }
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

OSChina 周日乱弹 —— 那么长的绳子,你这是放风筝呢

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @ 巴拉迪维:黑豹乐队的单曲《无地自容》 耳畔突然响起旋律,是那首老歌。中国摇滚有了《一无所有》不再一无所有;中国摇滚有了《无地自容》不...

小小编辑
55分钟前
65
1
《吐血整理》-顶级程序员书单集

你知道的越多,你不知道的越多 给岁月以文明,而不是给文明以岁月 前言 王潇:格局决定了一个人的梦想,梦想反过来决定行为。 那格局是什么呢? 格局是你能够看见的深度、广度和密度。 王潇认...

敖丙
2019/12/11
8
0
我可以在Android版式中加下划线吗? - Can I underline text in an Android layout?

问题: 如何在Android布局xml文件中定义带下划线的文本? 解决方案: 参考一: https://stackoom.com/question/A31z/我可以在Android版式中加下划线吗 参考二: https://oldbug.net/q/A31z/...

法国红酒甜
58分钟前
26
0
干掉ELK | 使用Prometheus+Grafana搭建监控平台

什么是Prometheus? Prometheus是由SoundCloud开发的开源监控报警系统和时序列数据库(TSDB)。Prometheus使用Go语言开发,是Google BorgMon监控系统的开源版本。 Prometheus的特点 · 多维度...

木九天
今天
34
0
拉勾网拉你上勾

预览 需求简介 拉勾网是一个互联网行业的一个招聘网站,上面有许多职位,于是乎,小编想提取指定职位的基本信息(职位名,薪水,工作经验,工作地点,教育背景),然后插入 MongoDB 数据库,...

木下瞳
2019/04/17
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部