bzoj 3874: [Ahoi2014]宅男计划-白红宇

bzoj 3874: [Ahoi2014]宅男计划

阅读量：4317 次

发布时间：2019-06-06

本文共 1644 字，大约阅读时间需要 5 分钟。

$solution:$

看到这一题题面，莫名想到了（蔬菜），于是莫名开始恐慌。考场上只知道有个贪心计算快递小哥来一次，我要买能活n天的最小花费，却没想到还有一个三分法来枚举快递小哥来的次数！

首先我们可以脑补一下，快递小哥来的次数，和宅男活的总天数是成一个二次函数关系的。就像快递小哥来的次数少，那宅男多数的钱只能分到这么少的购买次数中，因为便宜的保质期短，每次必然会买一些保质期长价格贵的食物；当快递小哥来的次数多了，那我的钱可以分配到很多次购买机会中，是可以每次买些便宜的，可是你就会发现钱不多了（都给快递小哥付运费了！）所以我们三分找到中间的那一个平衡点(合理的购买次数能（钱尽其用）活得更久！！)

这是三分，那本题贪心贪在哪儿呢？我们读题发现，他给你的食品中肯定有一些垃圾食品（价格贵，保质期又短），我们可以进行筛选：单调队列，先将食品按保质期从大到小排序，然后放入以价格单调增的队列中去（因为后面放进取得食品保质期一定更长（排了序的），一但价格还比前一个低，就可以取代前一个食品）

然后还有一个贪心，就是在$check()$函数中，计算能活的最长天数时，只要在保质期内，我一定买最便宜的。就像我现在经筛选后有两个食品，一个保质期为5，价格为4，另一个保质期为8，价格为7，那我$[1,6]$天一定买第一个，$[7,9]$天一定买第二个！因为我们单调栈中时间从小到大，所以每次算活得最长天数时复杂度$O(n)

$再加上三分的复杂度，本题刚好够用！

然后对代吗做个解释：因为根据题意，保质期为1天的食品，可以留两天！！！（被这个坑惨了）所以我们在读入时干脆就给保质期加一，这样方便运算！然后解释一下我的$check（）$函数：

我的$check()$买东西时，是同步的，如果买一个食品，那快递小哥来的$x$次都买这个食品（那个$if$除外）

$left:$我还剩下的钱的数量，（因为特性1，所以每一次都要减去我买的食品的价格乘以它的数量再乘以$x$天）

$now：$我同步买东西能同步维持的天数目前是多少

$day:$我有几天需要买这一种食品（如果没有足够的钱贪心的买，就会转到$if$中去）

$tot:$我总共能维持多少天

$if(now<b[i].t):$我没足够的钱来$x$天同步买一个东西，那我能买几天买几天，然后$return $

接下来一切以代码为准：

$code:$

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define ll long long#define db double#define inf 0x7fffffff#define rg register intusing namespace std;struct su{ ll v,t;}a[215],b[215];ll n,top;ll ans,m,f;//如题inline ll qr(){//快读，可以忽略 char ch; while((ch=getchar())<'0'||ch>'9'); ll res=ch^48; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch^48); return res;}inline bool cmp(su x,su y){return x.t

转载于:https://www.cnblogs.com/812-xiao-wen/p/10332544.html

你可能感兴趣的文章

\(solution:\)

\(code:\)