首页 > 其他分享 >Monster (贪心)

Monster (贪心)

时间:2022-10-25 12:02:34浏览次数:49  
标签:begin end Monster kn k2 m1 怪物 贪心


Monster

【题目描述】

明明的手机上有这样一个游戏,有一排n个怪物,每个怪物的血量是mi。现在明明可以射出k个伤害均为p的火球射向某些怪物。当某个火球射到第i个怪物,除了这个怪物会掉血p以外,它左边的第j个怪物(j<=i),也会遭到Max(0, p - (i - j)* (i - j))的溅射伤害。当某个怪物的血量为负的时候,它就死了,但它的尸体已然存在,即其他怪物不会因为它死而改变位置。

明明想用这k 个火球消灭掉所有的怪物,但他同时希望每个火球的伤害p能尽可能的小,这样他才能完美过关。

【输入数据】

第一行两个数 nk (1≤ n ≤ 50000, 1 ≤ k ≤ 100000)。

第二行n个数m1m2,...mn (1 ≤ mi ≤ 109),表示每个怪物的生命值。

【输出数据】

最小的符合要求的p值。

【样例输入】

3 1

1 4 5

【样例输出】

6

【数据范围】

1 ≤ n ≤ 50000, 1 ≤ k ≤100000,1 ≤ mi ≤109

30%的数据,n ≤ 500


贪心+二分 显然 最右边那个妖怪一定是被轰击致死的


Program monster;
const
INF=1000000000;
var
n,k,i,j:longint;
m1,a:array[1..50000] of longint;
procedure sort(l,r:longint);
var
i,j,m,k2,kn:longint;
begin
if l=r then
begin
writeln(l);
close(input);
close(output);
halt;

end;

m:=(l+r) shr 1;
for i:=1 to n do a[i]:=m1[i];
k2:=k;
for i:=n downto 1 do
if a[i]>0 then
begin
kn:=k2;
dec(k2,a[i] div m);
a[i]:=a[i] mod m;
if a[i]>0 then
begin
dec(k2);
dec(a[i],m);
end;

if k2<0 then sort(m+1,r);
kn:=kn-k2;
j:=i-1;
while (m-sqr(i-j)>0) and (j>=1) do
begin
if (kn*(a[j]-m+sqr(i-j))<0) then a[j]:=0 else
dec(a[j],kn*(m-sqr(i-j)));
dec(j);
end;

end;
sort(l,m);


end;
begin
assign(input,'monster.in');
assign(output,'monster.out');
reset(input);
rewrite(output);

read(n,k);
for i:=1 to n do
begin
read(m1[i]);
inc(m1[i]);
end;


sort(1,inf+1);


end.





标签:begin,end,Monster,kn,k2,m1,怪物,贪心
From: https://blog.51cto.com/u_15724837/5794418

相关文章

  • BZOJ 1007(水平可见直线-斜率排序+栈贪心)
    1007:[HNOI2008]水平可见直线TimeLimit: 1Sec  MemoryLimit: 162MBSubmit: 1830  Solved: 656[​​Submit​​][​​Status​​][​​Discuss​​]......
  • 贪心算法-455分发饼干
    题目455分发饼干假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干......
  • 第三个贪心
    A-汽车加油问题#include<bits/stdc++.h>usingnamespacestd;inta[5010],n,k;signedmain(){cin>>n>>k;for(inti=0;i<=k;i++)......
  • 贪心算法 455
    455.分发饼干classSolution{publicintfindContentChildren(int[]g,int[]s){Arrays.sort(g);//孩子列表Arrays.sort(s);//饼干列表......
  • Madoka and the Sixth-graders (全排列队列,每一个点可以向外连1条线题型+倍增法处理
    题意:Madoka的教室里有 nn 个座位,一开始,编号为 ii 的座位上坐着编号为 b_i(1\leb_i\len)bi​(1≤bi​≤n) 的同学。门外有排成一队的,编号从 n+1n+1 开始的,......
  • Madoka and Childish Pranks (贪心+逆序即可)
    题目大意: 给定一个01矩阵,其中0代表黑色,1代表白色Madoka要对一个同样大小的0矩阵染色,每次染色可以将一个矩形染成国际象棋的颜色(-1)^(x+y)的颜色(1白2黑)现......
  • Scapegoat Gym - 101775B (贪心+推公式)
    题目链接https://vjudge.csgrandeur.cn/problem/Gym-101775B原文题意:现在某人闯祸了,产生了N个锅,每个锅有个严重点数,现在可以安排M个替罪羊去背锅。每个替罪羊最多......
  • 贪心算法
    贪心算法所采用的策略,是保证每次操作都是局部最优,从而使最后结果是全局最优。1.n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求,......
  • Snowy Mountain (找规律来贪心+ 多源特殊bfs+根号n)
    题目大意:给定一棵 nn 个点的树,其中每个点可能是黑色或白色。一个点的高度定义为其距离最近黑色节点的距离。你初始在 ii 号节点上,势能为 00,可以做以下两种操作:......
  • 【UOJ 710】魔塔 OL(贪心)(四毛子分块)
    魔塔OL题目链接:UOJ710题目大意有一个三维的网格,点有权值a,b,维护三个操作:加入一个点,删除一个点,把某一个(1,x)(1,y)(1,y)立方体里面的点拿出来,做一次操作的最小初......