炸弹 (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。
输出格式
输出共一行，包含一个整数，为调配两个炸弹时所需的最小总材料量。
测试样例
| Input | Output |
|---|---|
| 5 | |
| 0 3 1 | |
| 0 1 2 | |
| 5 1 3 | |
| 1 2 4 | |
| 4 3 5 | 54 |
| 5 | |
| 0 2 9 | |
| 4 1 1 | |
| 2 3 1 | |
| 2 0 1 | |
| 2 1 10 | 121 |
思路：
1.按x排序，寻找每一个分界线的最小总材料量。
2.注意！！这里的网格是平面直角坐标系的网格，不是二维数组，我这里卡了好久
3.此代码还是暴力分，还未更新，作者考完期末考再来更新
#include<iostream>
#include<algorithm>
using namespace std;
struct Node{int x;int y;int value;
};
int n;
int sum1,sum2;
const int L = 1e4+1;
Node arr[L];
int list[L];
bool compare(Node a,Node b)
{return a.x < b.x;
}
int cntl(int x)//处理左半部分
{int high = -1;int low = 1e9;int left,right;int S,D = -1;right = arr[x].x;//左半部分，靠最右边的边界 left = arr[1].x;//左半部分，靠最左边的边界for(int i = 1 ; i <= x ; i++){high = max(high,arr[i].y);//找出高最大 low = min(low,arr[i].y);//找出底最小 D = max(D,arr[i].value);//找出D最大 }int len = right-left+1;int width = high - low+1;S = len*width;return S*D;
}
int cntr(int x)//处理右半部分
{int high = -1;int low = 1e9;int left,right;int S,D = -1;right = arr[n].x;//右边部分，靠最右边的边界 left = arr[x].x;for(int i = x ; i <= n ; i++){high = max(high,arr[i].y);//找出高最大 low = min(low,arr[i].y);//找出底最小 D = max(D,arr[i].value);//找出D最大}int len = right-left+1;int width = high - low+1;S = len*width;return S*D;
}
int main(void)
{cin >> n;for(int i = 1 ; i <= n ; i++)//为x排序 有1~n个怪物位置 {cin >> arr[i].x >> arr[i].y >> arr[i].value;}sort(arr+1,arr+1+n,compare);//按x大小排序1~n个int all = 1e9;for(int j = 1 ; j < n ; j++)//以x轴，第i个怪物,所以是x{if(arr[j].x == arr[j+1].x)continue;sum1 = cntl(j);//左半部分右闭 sum2 = cntr(j+1);//右半部分左开 all = min(all,sum1+sum2); } cout << all << endl;return 0;}
