【Gym-101775 C】Traffic Light【思维】

84 阅读 0 评论 56 点赞

我是靠谱客的博主安详电灯胆，这篇文章主要介绍【Gym-101775 C】Traffic Light【思维】，现在分享给大家，希望可以做个参考。

题意：

从家到公司，一共 $n$ 个红绿灯，一共 $n + 1$ 段路。你可以设置每一个红绿灯的开始时间，且每个红绿灯的绿灯时间+红灯时间一致。对于每一种设置，从家出发的时间都任意，因此一定存在一个最坏的情况。先要求输出最坏情况的最小值为多少。 $(1 \leq n \leq 1000)$

思路：

比赛时无头绪。题意也看了半天才明白。

比赛后知道了解法。答案即为所有路上时间之和加上最大的红灯时间。

但是为什么呢？

其实这是一道构造问题，构造问题的关键在于限制条件。

我们通过调整每个红绿灯的开始时间，使得通过第 $i$ 个红绿灯之后即可立刻到达第 $i + 1$ 个红绿灯。因此我们最多等待一个红绿灯，接下来即可畅通无阻。因此最坏情况就是加上红绿灯的最大值。
在这里插入图片描述

但是这就是答案吗？肯定是。因为无论你怎么设置，由于出发时间任意，我都一定可以让你在某个红绿灯处完整等完这个红绿灯。所以只用等最大的红绿灯就是最后的答案。

总结：

一个构造思维题通过题意的复杂性伪装成了一个或暴力或 $D P$ 或贪心的问题，迷惑选手。

这题一个很关键的地方在于你可以任意设置红绿灯的开始时间，任意设置！任意设置！任意设置！如果枚举所有的设置必然不可能，因此可以考虑先猜一种比较好求解的设置，然后求最坏情况。

构造问题主要要求就是构造的一定要特殊，好求。将题目初始的一大堆变量全部干掉。

因此总结一下，解决此题，主要思考方法应该是：

小数据开始考虑，一个红绿灯，两个，三个…从小数据中找规律。
大胆构造特殊情况，将原来的 $n$ 个变量全都限制住。在特殊情况下考虑答案，在反证这个构造就是最优答案。

构造思维题继续加油！

代码：

复制代码

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
#include <bits/stdc++.h>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const db EPS = 1e-9;
using namespace std;

int n;
db sum;

int main()
{
	int _; scanf("%d",&_);
	rep(Ca,1,_){
		scanf("%d",&n);
		sum = 0;
		rep(i,1,n+1){
			db tp; scanf("%lf",&tp);
			sum += tp;
		}
		db maxn = 0;
		rep(i,1,n){
			db tp1,tp2; scanf("%lf%lf",&tp1,&tp2);
			maxn = max(maxn,tp2);
		}
		sum += maxn;
		printf("Case #%d: %.9fn",Ca,sum);
	}
	return 0;
}