ZOJ 3829 贪心 思维题

ZOJ 3829 贪心 思维题

大家好,又见面了,我是全栈君。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3829

现场做这道题的时候,感觉是思维题。自己智商不够。不敢搞,想着队友智商好,他们搞吧。可是没出来这题……

以后不论什么时候,都自信点….该想的还是好好自己想,这类题感觉就是先去找性质,然后一点点找规律,假设必要的话。自己提出一点猜想。然后假设自己举不出来反例,就临时觉得是正确的

下午搞了一下午。发现还是悲剧,晚上參考了两个题解

http://blog.csdn.net/keshuai19940722/article/details/40039975

事实上至少能够总结出来一下规律:
1、必须num(*)<num(数字)

2、前面全是数字的后面全是*是合法的。就是说,假设须要交换的话,能够把*全换到最后,就是把*和最后的数字交换位置,反正每次耗费都是1

3、由于交换一次耗费为1,插入一次耗费也是1,所以假设不满足规律1,能够先插入,又由于规律2,所以把数字在一開始就所有插入到最前面,用栈模拟后缀表达式的验证过程,假设缺数字。就把最后的数字和当前的*交换位置,根据是规律2.不会缺星号的。由于连续的数字能够当做同一个数字


以上三条足够解决这个问题

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 1000+50;
#define CL(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define IN(s) freopen(s,"r",stdin)

char str[MAXN],sta[MAXN*10];
int pos[MAXN*10];
int len,numa,numb,tp,postp;

void init()
{
    tp=postp=0;
    numa=numb=0;//
    scanf("%s",str);
    len=strlen(str);
}

ll solve()
{
    for(int i=0;i<len;i++)
    {
        if(str[i] == '*')
            numa++;
        else
        {
            numb++;
            pos[postp++]=i;
        }
    }
    if(numa == 0)return 0;//****特判
    ll ans=0;
    tp=max(numa+1-numb,0);//假设数字多。总是能够组合出来的
    //在开头补上数字
    ans=(ll)tp;
    for(int i=0;i<len;i++)
    {
        if(str[i] == '*'){
            if(tp>=2)tp--;
            else{
                str[pos[postp-1]]='*';
                postp--;
                tp++;
                ans++;//交换没有强调相邻
            }
        }
        else
            tp++;
    }
    if(ans==0 && str[len-1]!='*')ans++;//
    return ans;
}

int main()
{
    //IN("K.txt");
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        init();
        printf("%lld\n",solve());
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116268.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 目前主流的app开发方式

    目前主流的app开发方式移动应用开发三种方式比较随着H5标准的发布以及推广,使得移动应用的开发也受到了很大影响,出于效率、成本等等的原因,移动应用的开发不在完全依赖于“原生”。今天就简单总结一下目前的三大主流移动应用开发类型。APP,一般认为是mobileapplication,也就是移动移动应用程序。1.NativeApp:本地应用程序(原生App)NativeApp是一种基于智能手…

  • kafka删除topic数据_kafka查看topic列表

    kafka删除topic数据_kafka查看topic列表 kafka删除topic提示markedfordeletion [html] viewplain copy [root@logSer config]# kafka-topics.sh –delete –zookeeper localhost:2181 –topic test-group        Topic test-group…

  • dex字符串解密_DEX文件混淆加密

    dex字符串解密_DEX文件混淆加密现在部分app出于安全性(比如加密算法)或者用户体验(热补丁修复bug)会考虑将部分模块采用热加载的形式Load。所以针对这部分的dex进行加密是有必要的,如果dex是修复的加密算法,你总不想被人一下就反编译出来吧。当然也可以直接用一个加密算法对dex进行加密,Load前进行解密就可以了,但是最好的加密就是让人分不清你是否加密了。一般逆向过程中拿到一个可以直接反编译成java…

  • floyed详解[通俗易懂]

    floyed详解[通俗易懂]显然Floyed算法是一个简短而好理解的算法,这里指的好理解是因为Floyed的代码长度不大,实在没理解都可以背下来,所以说是好理解,实际上是真的好理解吗?我们来看看最基础的FloyedFloyed是什么?自然是用来求多源最短路的啦,时间效率是O(n^3),有人会问那我不对每个点做一遍SPFA或dijkstra堆优化,时间效率是O(n^2logn)那不是快很多?实际上因为Floyed

  • 简述CORBA开发步骤_发散思维的简单例子

    简述CORBA开发步骤_发散思维的简单例子因为对CORBA分析的需要,这里写一个简单的CORBA例子。从JDK1.2开始,JDK中集成了ORB的实现,本例子使用了JDK1.7,对于JDK1.2+应该都没有问题。这个例子实现一个简单的加减乘除的

  • SpringBoot——SpringBoot整合Mybatis

    SpringBoot——SpringBoot整合MybatisSpringBoot——SpringBoot整合Mybatis

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号