洛谷 1485 火枪打怪
发布日期:2022-02-05 18:27:29 浏览次数:11 分类:技术文章

本文共 2767 字,大约阅读时间需要 9 分钟。

题目描述

LXL进入到了一片丛林,结果他发现有n只怪物排成一排站在他面前。LXL有一杆火枪能对付这些怪物。他知道从左至右数第i只怪物的血量是mi。现在LXL可以将一些子弹射向某个怪物。LXL可以控制他所发射的子弹数量及子弹的威力值。当某个子弹射到第i个怪物,如果这个子弹的威力值为p,除了这个怪物会掉p点血以外,它左边的第j个怪物(j<i),也会遭到Max(0, p - (i - j) * (i - j))的溅射伤害(好神奇的子弹)。当某只怪物的血量小于0时,它就死了,但它的尸体还在,即怪物的位置永远不会改变。LXL希望只用k发子弹,请你求出一个最小的正整数p,使LXL用k发子弹且每发子弹的威力值为p就可以消灭所有怪物。

输入格式

第一行,两个正整数n,k。

第二行,n个正整数,第i个正整数表示从左至右数第i只怪物的血量mi。

输出格式

一个正整数,表示子弹的最小威力值p。

样例输入 

3 1

1 4 5

样例输出

6

注释

对于30%的数据,n<=300。

对于100%的数据,n<=500000,k<=500000,1<=mi<=10^10

一看到这个题就想到了首先肯定打最右面的 打死一个向前走再打最后没死的。。。丧心病狂

然后伤害 就想到了二分

二分很简单 但是验证不简单

由于伤害向左溅射

一开始枚举每一个打的 然后将伤害向左溅射一次  时间复杂度约 N^2 * log N

然后只能过3个点

看题解上说的O(n)验证很厉害啊

节省时间就直接抄过来吧。。。

容易注意到随着p的增大,所需要的子弹数单调递减。于是我们便会想到二分答案,但这并不是难点,本题的难点在于:对于一个二分出的p,如何快速计算出它所需要的子弹数?
由于本题中子弹的溅射伤害只是向左,故很容易想到子弹应从右打起,打到怪物被消灭为止。但如果朴素计算溅射伤害,复杂度可能高达O(n^2),无法通过本题。所以我们需要一个更优的计算方法。
我们设对于二分出的p,射到从左到右第s个怪物身上的子弹数为kk[s]。对于p-(i-j)*(i-j)我们将它拆开,变成-j^2+2ij-i^2+p。对于第j个怪,它受到的溅射伤害应为-(kk[j+1]+...+kk[n])*j^2+2*(kk[j+1]*(j+1)+...+kk[n]*n)*j-(kk[j+1]*(j+1)^2+...+kk[n]*n^2)+(kk[j+1]+...+kk[n])*p。
这其实是把溅射伤害的值表示为一个二次函数。而二次函数每一项的系数都是可累加的,溅射伤害可以随着循环算出。而当p-(i-j)*(i-j)<0时,我们便需要把对应的i从系数中减去。每一位至多只会被减去一次,故总复杂度仍不变,对于一个二分出的p,计算出它所需要的子弹数的时间复杂度仍为O(n)

#include
#include
#include
#include
using namespace std;long long s[500011];int use[500011];int m,n,a,b,c;long long l,r,mid,ans;long long lim;long long life;long long T1,T2,T3,used;inline bool ok(){ long long a; memset(use,0,sizeof(use)); used=0;T1=0,T2=0,T3=0; for(a=m;a>=1;a--) { if(use[a+1]) { T1+=use[a+1]; T2+=use[a+1]*(a+1); T3+=use[a+1]*(a+1)*(a+1); } if(a+lim<=m&&use[a+lim]) { T1-=use[a+lim]; T2-=use[a+lim]*(a+lim); T3-=use[a+lim]*(a+lim)*(a+lim); } life=mid*T1-a*a*T1+2*a*T2-T3; if(s[a]>=life) { use[a]=(s[a]-life)/mid+1; used=used+use[a]; } if(used>n)return false; } return true;}int main(){ scanf("%d%d",&m,&n); for(a=1;a<=m;a++) { scanf("%d",&s[a]); r+=s[a]; } l=s[m]/n; r=r/n+1; while(l<=r) { mid=(l+r)>>1; lim=(long long)sqrt(mid)+1; if(ok()) { ans=mid; r=mid-1; } else l=mid+1; } cout<
<

一开始写的渣N^2的验证

bool ok(){    int a,b;    long long dec;    memset(hurt,0,sizeof(hurt));    memset(use,0,sizeof(use));    int used=0;    for(a=m;a>=1;a--)    {        if(s[a]>=hurt[a])use[a]=(s[a]-hurt[a])/mid+1;        used=used+use[a];        if(used>n)return false;        for(b=a-1;b>=1;b--)        {            dec=mid-d(a-b);            if(dec<=0)break;            hurt[b]=hurt[b]+dec*use[a];        }    }    return true;}

转载地址:https://blog.csdn.net/li412302070/article/details/13613467 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:洛谷 1761 正方形
下一篇:Curves

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月13日 00时17分41秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java怎样将日期本土化_Java中的日期操作 2019-04-21
java生产者消费者模型到精通_java生产者消费者模型 2019-04-21
java 执行 awk_3.1 biostar lesson3 linux学习日记;java版本;awk 2019-04-21
java二叉树求权值_百度笔试题目:二叉树路径权值和【转】 2019-04-21
欧亚马 java折叠车_如何选择欧亚马折叠车? 2019-04-21
python函数代码块以什么开头_Python初体验-开篇 代码全析 2019-04-21
java闹钟程序设计_JAVA课程设计_闹钟的设计与实现项目-报告_附源代码.doc 2019-04-21
java中的无效的列类型_java.sql.SQLException: 无效的列类型: 1111 2019-04-21
php rewrite url_PHP_URL Rewrite的设置方法,URL Rewrite需要服务器的支持! - phpStudy 2019-04-21
php读取大文件某行内容,PHP读取和修改大文件的某行内容_PHP教程 2019-04-21
打印php错误日志,php怎样打印错误日志 2019-04-21
Calendar导入java,Java程序使用Calendar.add()方法将分钟添加到当前时间 2019-04-21
mysql中用户线程作用,mysql用户线程的建立与用户线程的状态源码解析 2019-04-21
php页面引用公共文件,WeiPHP插件模板中快速引入公共模板文件 2019-04-21
php tracy,admin.php 2019-04-21
php访问父类的所有属性,php – 在父类中使用$this仅在子类中显示父类属性 2019-04-21
oracle比较强大的函数,SQL和ORACLE函数比较 2019-04-21
oracle12c order by,oracle 数据库中order by 的一些高级用法 2019-04-21
oracle8i substr,Oracle中的INSTR,NVL和SUBSTR函数的用法详解 2019-04-21
导出oracle11g的空表,轻松解决oracle11g 空表不能 exp 导出 的问题。 2019-04-21