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)


相关推荐

  • VS中新建Qt项目工程后显示无法打开源文件“QtWidgets/QApplication”的解决方案「建议收藏」

    VS中新建Qt项目工程后显示无法打开源文件“QtWidgets/QApplication”的解决方案「建议收藏」环境:VS2015+Qt5.6在vs中新建工程后一般都会显示无法打开源文件“QtWidgets/QApplication”,就像这样:这是什么原因呢?这是因为,新建Qt项目时VC++包含目录没有自动包含Qt所需要的头文件路径,需要手动添加,具体操作步骤如下:1.在工程中右击项目,点击属性。2.选择VC++目录->包含目录,按图所示步骤操作。3.选择Q…

  • ASP.NET使用AJAX应注意IIS有没有.ashx扩展

    ASP.NET使用AJAX应注意IIS有没有.ashx扩展

    2021年11月17日
  • vue 刷新保存数据_vuex数据何时清除

    vue 刷新保存数据_vuex数据何时清除在项目中我们通常会遇到这样一个情况,客户不允许把信息存储在sessionStorage/localStorage因为这样会暴露一些存储信息,安全起见只能存储在vuex里面,但是vuex刷新之后state里面的信息依旧会被清除,我们的思路是刷新之前把所有的数据存储在localStorage里面,刷新后取出里面的数据,并清除local/session里面的记录,这种全局的我们可以放在app.vue里面,下面是代码实现//app.vuecreated(){//在页面

    2022年10月16日
  • mysql索引详解「建议收藏」

    一、MySQL三层逻辑架构MySQL的存储引擎架构将查询处理与数据的存储/提取相分离。下面是MySQL的逻辑架构图:一、对比InnoDB与MyISAM1、存储结构MyISAM:每个MyISAM在磁盘上存储成三个文件。分别为:表定义文件、数据文件、索引文件。第一个文件的名字以表的名字开始,扩展名指出文件类型。.frm文件存储表定义。数据文件的扩展名为.MYD(MYData)。索引文件的扩展名是.MYI(MYIndex)。InnoDB:所有的表都保存在同一个数据文件中(也可能是多个

  • 单片机控制步进电机

    单片机控制步进电机简介:用单片机控制步进电机正转反转加速减速;由LCD1602实时显示步进电机的状态;F-正转,B-反转;数字越大,转速越大;仿真原理图如下:MCU和LCD1602显示模块:ULN2803驱动和步进电机模块:C语言代码如下:/*—————————–FileName:StepperMotor.hFunction:函数头文件Autho…

  • Oracle 触发器详解(trigger)「建议收藏」

    Oracle 触发器详解(trigger)「建议收藏」文章目录1概述2触发器管理2.1创建触发器2.1.1foreachrow2.1.2follows2.1.3when2.2查询触发器2.3删除触发器2.4常用属性2.4.1inserting、updating、deleting2.4.2now、old3触发器分类3.1DML触发器3.1.1单列触发:of列名3.2DDL触发器3.3Databse触发器3.4insteadof替换触发器1概述1.触发器是什么..

发表回复

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

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