「FJ互测」油滴扩展·改

2014年8月30日3,1790

「题目描述」

在大小A*B的paper中,将有N个圆形油滴。

已知第i个油滴信息如下: 中心位置:(Xi,Yi),开始扩散时间:Ti,扩散T时间后的面积: Ai*T

求paper被油滴完全覆盖的最短时间。

提示:保证有解

「输入」

一行三个非负整数A,B,N

接下来N行,每行四个非负整数Xi,Yi,Ti,Ai

「输出」

完全覆盖的最短时间,向上取整输出

「样例输入」

1000 1000 1

0 0 0 2

「样例输出」

3141593

「数据规模」

  • 对20%的数据,所有输入数字不超过10
  • 对另30%的数据,所有输入数字不超过100
  • 对所有数据,所有输入数字不超过1000

「题解」

 A:随机方法

1、 对于题意,我们发现“纸张被油滴完全覆盖”即为“纸张上一点最晚被覆盖”

2、 这是一个平面上的最优化问题,随意套用模拟退火等随机算法得解

我写了个随机起点的爬山。。。但是效果很差T T

std是秒杀啊。。。结果打开一看,区别似乎就在于他是上下左右随机走,我是随机一个方向。。。

接着一看。。。我随机的向量都是正的,不停往右上方走!!!!

avatar
  Subscribe  
提醒