炸弹 (boom.c)（100分双端递推+分割线优化）

炸弹 (boom.c)

时间限制: 800ms
内存限制: 256000KiB
进度: 57/12406 = 0.5%

题目描述

出题助教: Sakiyary
验题助教: Corax、XiEn、ErinwithBMQ、runz、MacGuffin、Bob

维多利亚的腐烂荒野上出现了 N 个魔物，你和小维需要抓紧时间调配炸弹对付它们。

荒野可以视为一张方格图，(x_i, y_i, h_p_i) 表示魔物 i 出现在方格 (xi​,yi​) 上，其生命值为整数 h_p_i。每个方格最多出现一个魔物。

你们可以调配炸弹的 爆炸范围 与 爆炸伤害 两个参数：

• 爆炸范围 是一个任意位置、由方格作为单元组成的、任意大小的矩形，最小为 1×1 的方格；
• 爆炸伤害 是一个整数值。

为了消灭爆炸范围内的所有魔物，爆炸伤害至少要等于该爆炸范围内魔物生命值的最大值。

假设炸弹 爆炸范围 的面积为 S，爆炸伤害为 D，则调配该炸弹所需要的材料量为 S×D。

为了抓紧时间并减少炸弹的总材料消耗，你们决定调配两个炸弹，将魔物划分为左右两批，两人各用一个炸弹对付其中一批，即两个炸弹的爆炸范围在 x 轴上的投影不重叠。

输入格式

输入共 N+1 行:

• 第一行包含一个正整数，表示魔物的数量 N;
• 接下来有 N 行，每行包含三个非负整数，以空格隔开，分别表示当前魔物 i 所处方格的 xi​ 坐标、yi​ 坐标以及魔物的生命值 hpi​。

输出格式

输出共一行，包含一个整数，为调配两个炸弹时所需的最小总材料量。

测试样例

思路：

1.暴力会超时，所以我们需要优化寻找最大hp，最高，最低。我们可以采用递推的方法，以左半部分举例子，储存好前一步的hp，高，低，对于向右移动的x坐标划分线，我们只要比较新的x轴坐标划分线的hp，高，低。与原先比较即可。

2.由于暴力分的数组，会存在连续相等的x坐标，对于递推是很不方便的。所以我换了一种去重储存怪物坐标的点。用一个结构体类型的数组，储存每一个x坐标分割线上的最高值，最低值还有最大的HP值。这样就可以进行递推了。

3.但是很快，我们就会发现，只能对左半部分的进行递推，右半部分却只能遍历寻找上部分，下部分，最大HP。由于分割线是两个部分一起的，左半部分右边界是闭，右半部分左边界是开,所以我们可以从右往左递推，以及之前的从左往右递推。记录每一个x作为分割线上，左（右）部分需要的材料。这样就需要两个数组来储存。最后遍历存在的最左边界x到最右边界x，依次相加两个部分的材料，通过比较求出最小材料。

4.有人可能会问？好像只用到了排序的最左边界和最右边界啊？那是不是只要找到最左边界x最右边界x就行了，不需要特地排序，我的理解是，有些x分割线上是没有怪兽的，以存在怪兽的分割线更快找到最小材料。所以只要在有怪物的x分割线上做文章就好了。

代码如下：

#include<iostream>
#include<vector> 
#include<algorithm>
using namespace std;
struct node{
	int yhigh =-1e9 ;
	int ylow = 1e9;
	int HP;
};
int ans = 1e9;
int n;
const int L = 1e6;
int monster[L];
bool mem[L];//去重x坐标数组 
int left_half[L];//记录每一个x分割线的左半部分数组 
int right_half[L]; //记录每一个x分割线的右半部分数组 
node list[L]; 
int num = 0;//计数存在的x数量 

int Dl;//左半部分最大生命值 
int high_left = -1;
int low_left = 1e9;
int cntl(int x)///左半部分 
{
	int S; 
	int left = monster[1];
	int right = x;
	high_left = max(high_left,list[x].yhigh);
	low_left = min(low_left,list[x].ylow);
	S = (right - left +1) * (high_left - low_left + 1);
	Dl = max(Dl,list[x].HP);
	
/*	cout << "左半部分左边界：" << left << endl;
	cout << "左半部分右边界：" << right << endl;
	cout << "左半部分上边界：" << high_left << endl;
	cout << "左半部分下边界：" << low_left << endl;
	cout << "左半部分高度差：" << high_left - low_left + 1 << endl;
	cout << "左半部分长度差：" << right - left + 1 << endl;
	cout << "左半部分最大生命值：" << Dl << endl;*/
	return S*Dl;
}

int Dr;//右半部分最大生命值
int high_right = -1;
int low_right = 1e9;
int cntr(int x)//右半部分 
{
	int S;
	int left = x;
	int right = monster[num];
	high_right = max(high_right,list[x].yhigh);
	low_right = min(low_right,list[x].ylow);
	S = (right - left + 1) * (high_right - low_right + 1);
	Dr = max(Dr,list[x].HP);
	return S*Dr;
 } 
int main(void)
{
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
	{
		int x,y,hp;
		cin >> x >> y >> hp;
		if(!mem[x])
		{
			mem[x] = true;
			monster[++num] = x;//储存存在的x坐标 	
//			cout << "存入" << x << "在" << num <<endl;
		}
		if(list[x].yhigh < y)//储存x坐标上的最高点 
		list[x].yhigh = y;

		if(list[x].ylow > y)//储存x坐标上的最低点 
		list[x].ylow = y;

		if(list[x].HP < hp)//储存x坐标上最大的生命值 
		list[x].HP = hp; 
	}
	
	sort(monster+1,monster+1+num); //升序排序出现的坐标x分割线
	
/*	for(int i = 0 ; i <= monster[num] ;i++)
	{
	cout << "第" << i << "为分界线的最高" << list[i].yhigh << " " << endl;//正确  
	cout << "第" << i << "为分界线的最低" << list[i].ylow << " " << endl;  //正确 
	}*/

//	cout << monster[i] << " " << endl; 排序正确 

	for(int i = 1 ; i <= num - 1 ; i++)//左半部分右边界是闭 
	{
		left_half[monster[i]] = cntl(monster[i]);
	} 
	for(int i = num - 1 ; i >= 1 ; i--)//右半部分左边界是开 
	{
		right_half[monster[i]] = cntr(monster[i+1]);
	}
	
	for(int i = 1 ; i <= num - 1 ; i++)
	{
		ans = min(ans,left_half[monster[i]] + right_half[monster[i]]);//比较每一个x分割线的左半部分和右半部分的和，找出最小。 
	}
	cout << ans;
	return 0;
 }

因为只测试过样例，有错误请指出！