列表

详情

NC20356. [SDOI2013]保护出题人

描述

出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。

参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。

僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。

第一关，一只血量为a1点的墦尸从距离房子x1米处速接近，你们放置了攻击力为y1点/秒的植物进行防御；
第二关，在上一关基础上，僵尸队列排头增加一只血量为a2点的僵尸，与后一只僵尸距离d米，从距离房x2米处匀速接近，你们重新放置攻击力为y2点/秒的植物；
……；
第n关，僵尸队列共有n只僵尸，相邻两只僵尸距离d米，排头僵尸血量为an点，排第二的 僵尸血量an−1，以此类推，排头僵尸从距离房子xn米处匀速接近，其余僵尸跟随排头同时接近，你们重新放置攻击力为yn点/秒的植物。

每只僵尸直线移动速度均为1米/秒，由于植物射击速度远大于僵尸移动速度，可忽略植物子弹在空中的时间。所有僵尸同时出现并接近，因此当一只僵尸死亡后，下一只僵尸立刻开始受到植物子弹的伤害。

游戏得分取决于你们放置的植物攻击力的总和，和越小分数越高，为了追求分数上界，你们每关都要放置攻击力尽量小的植物。

作为SDOI2013的参赛选手，你们能保护出题人么？

输入描述

第一行两个空格隔开的正整数n和d，分别表示关数和相邻僵尸间的距离。
接下来n行每行两个空格隔开的正整数，第i + 1行为Ai和 Xi，分别表示相比上一关在僵尸队列排头增加血量为Ai点的僵尸，排头僵尸从距离房子Xi米处开始接近。

输出描述

一个数，n关植物攻击力的最小总和 ，保留到整数。

示例1

输入: 

5  2
3  3
1  1
10 8 
4  8
2  3

输出: 

7

说明:

第一关：距离房子3米处有一只血量3点的僵尸，植物最小攻击力为1.00000；
第二关：距离房子1米处有一只血量1点的僵尸、3米处有血量3点的僵尸，植物最小攻击力为1.33333；
第三关：距离房子8米处有一只血量10点的僵尸、10米处有血量1点的僵尸、12米处有血量3点的僵尸，植物最小攻击力为1.25000；
第四关：距离房子8米处有一只血量4点的僵尸、10米处有血量10点的僵尸、12米处有血量1点的僵尸、14米处有血量3点的僵尸，植物最小攻击力为1.40000；
第五关：距离房子3米处有一只血量2点的僵尸、5米处有血量4点的僵尸、7米处有 血量10点的僵尸、9米处有血量1点的僵尸、11米处有血量3点的僵尸，植物最小攻击力 为2.28571。
植物攻击力的最小总和为7.26905。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 36ms, 内存消耗: 2680K, 提交时间: 2021-02-15 09:00:18 

#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
using namespace std;
const int maxn=100005;
int n,top,l,r,m1,m2;
db x[maxn],y[maxn],f[maxn],a[maxn],X[maxn],ans,d;
db calc(int i,int j)
{
	return (f[i]-y[j])/(X[i]+i*d-x[j]);
}
bool check(db x1,db y1,db x2,db y2,db x,db y)
{
	return (x1-x)*(y2-y)-(x2-x)*(y1-y)<0;
}
int main()
{
	scanf("%d%lf",&n,&d);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&a[i],&X[i]);
		f[i]=f[i-1]+a[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(;top>1&&check(x[top],y[top],i*d,f[i-1],x[top-1],y[top-1]);
		top--);
		y[++top]=f[i-1];
		x[top]=i*d;
		for(l=1,r=top,m1=l+(r-l)/3,m2=r-(r-l)/3;r-l>2;m1=l+(r-l)/3,m2=r-(r-l)/3)
		if(calc(i,m1)<calc(i,m2))
		l=m1;
		else
		r=m2;
		db tmp=-1e20;
		for(int j=l;j<=r;j++)
		tmp=max(tmp,calc(i,j));
		ans+=tmp;
	}
	printf("%.0lf\n",ans);
	return 0;
}

上一题

© 2024 nowcoder.com