华为OD机试：路灯照明问题(100分)

题目：
一条笔直的公路上安装了N个路灯，从位置0开始安装，路灯之间的距离是100m。每个路灯都有自己的照明半径，请计算第一个路灯和最后一个路灯之间，未照明区间的长度和。

输入描述：
第一行为一个数N，表示灯的个数，[1, 100000] 第二行为N个空格分隔的数，表示路灯的照明半径，[1,100*100000]
输出描述：
第一个路灯和最后一个路灯之间，未照明区间的长度和
举例：
输入：2 50 50 输出：0
输入：4 50 70 20 70 输出：20
输入：8 10 10 10 250 10 10 10 10 输出：160

实现思路

1. 要输出的是黑暗长度之和，所以首先需要构建出每个灯能够照射到的区间
2. 其次，如何知道什么时候有阴影，产生在什么位置呢？通过左右灯光位置进行判断，这里每次取两个灯的照射区间进行判断
3. 判断时具体分两种大情况：
   a. 前灯的后边界和后灯的前边界交叉，此时在两个灯之间所有位置没有阴影
   b. 前后边界不交叉，此时说明两个灯直接有空隙，这种情况下也需要进行分类
4. 判断时具体分两种大情况：
   a. 前灯的后边界和后灯的前边界，所在位置在一个区间内，比如[100,200]内，此时可以用后灯前边界-前灯后边界，就代表[100,200]区间内的阴影了，当然这只代表当前情况，每次更新时取阴影最小值
   b. 前灯的后边界和后灯的前边界，所在位置不在一个区间内，比如前灯后边界110，后灯前边界210，二者不在一个区间内，所以没有可比性，为什么呢？因为中间位置的灯的范围最小都是[199,201],所以这种情况下，没有更新的必要直接跳过
5. 最后将保存每个灯之间的阴影面积的数组求和即为目标值

#include
#include
#include
using namespace std;

int main()
{
	int n, r;
	cin >> n;//路灯个数
	vector<pair<int,int>> light;//每盏灯灯光所能照到的区间
	vector<int> res(n - 1, 100);//保存每个空隙当前的最小阴影
	int i = 0, N = n;
	while (n--)
	{
		cin >> r;//输入每个半径
		light.emplace_back(max(i * 100 - r, 0), min(i * 100 + r, (N - 1) * 100));
		++i;
	}
	for (int i = 0; i < light.size() - 1; ++i)
	{
		for (int j = i + 1; j < light.size(); ++j)
		{
			if (light[i].second >= light[j].first)//部分区间全部能照射到，这些区间都更新为0
			{
				int tmp = j-1;
				while (tmp >= i)
				{
					res[tmp] = 0;
					tmp--;
				}
			}
			else
			{
				int index1 = light[j].first / 100, index2 = light[i].second / 100;
				if (index1 > index2)continue;//不在一个区间，没必要比较
				res[index1] = min(res[index1],light[j].first - light[i].second);//在一个区间更新当前阴影
			}
		}
	}
	cout << accumulate(res.begin(), res.end(), 0);//求和
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43