AT_joisc2017_c 手持ち花火

前言

~~今典的拓拓拓拓展题~~

校内模拟赛搬了这道题，来写个题解。

正文

最优的方法是所有人朝着

k

走，与

k

相遇时就一起走，当

k

的火把熄灭时再把其他同位置的一个火把点燃，相当于每个火把加了

t

秒的总燃烧时间。因为所有人速度一样，因此相对位置不会变，即

i<j<k

时，若

i

能被点燃，那

j

也一定会被点燃过，右侧同理。得出可点燃的火把一定是一个区间

[l,r](l\le k\le r)

。

接下来求区间

[l,r]

能否能拓展至

[l-1,r]

或

[l,r+1]

。首先考虑

[l,r]

是否合法，若全都能点燃，其总燃烧时长为

t(r-l)

秒（最后一个点燃后直接结束），而所有的人聚在一起的时间即为

l

与

r

相遇的时间（所有人的相对位置不变），即

\dfrac{x_r-x_l}{2v}

。得到不等式

t(r-l)\ge \dfrac{x_r-x_l}{2v}

，当满足该不等式时，区间

[l,r]

是合法的。

继续拆解不等式，得到

2vtr-x_r\ge 2vtl-x_l

。

发现

v

具有单调性（若

v

可行则

v+1

也可行），因此考虑二分。于是问题就变成了给定一个非负整数

v

，初始

l=r=k

，每次可以

l\leftarrow l-1

或

r\leftarrow r+1

，且需满足

2vtr-x_r\ge 2vtl-x_l

，问是否可拓展至

l=1,r=n

。

这就是双序列拓展。将

x_{s\sim 1}

（

x_{1\sim s}

翻转）和

x_{s\sim n}

做双序列拓展即可。

AC Code

CPP

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e5 + 5 , inf = 1e18 + 7 , INF = inf * inf;
int x[N];
namespace Check
{
	int n , m;
	int a[N] , b[N] , prex1[N] , prey1[N] , nxtx1[N] , nxty1[N] , prex2[N] , prey2[N] , nxtx2[N] , nxty2[N];
	bool check1 (int px , int py)
	{
		if (px == 0 || py == 0) return 1;
		if (a[prex2[px]] < b[prey2[py]]) return check1 (prex2[px] - 1 , py);
		if (a[prex1[px]] < b[prey1[py]]) return check1 (px , prey1[py] - 1);
		return 0;
	}
	bool check2 (int px , int py)
	{
		if (px == n + 1 || py == m + 1) return 1;
		if (a[nxtx2[px]] < b[nxty2[py]]) return check2 (nxtx2[px] + 1 , py);
		if (a[nxtx1[px]] < b[nxty1[py]]) return check2 (px , nxty1[py] + 1);
		return 0;
	}
	bool check (int p , int siz , int t , int v)
	{
		a[0] = b[0] = -INF;
		n = p , m = siz - p + 1;
		a[n + 1] = b[m + 1] = INF;
		for (int i = p;i >= 1;i --) a[p - i + 1] = 2 * t * v * i - x[i];
		for (int i = p;i <= siz;i ++) b[i - p + 1] = 2 * t * v * i - x[i] + 1;
		prex2[0] = nxtx2[n + 1] = n + 1 , prey2[0] = nxty2[m + 1] = m + 1;
		for (int i = 1;i <= n;i ++)
		{
			prex1[i] = prex1[i - 1];
			if (a[prex1[i]] < a[i]) prex1[i] = i;
			prex2[i] = prex2[i - 1];
			if (a[prex2[i]] > a[i]) prex2[i] = i;
		}
		for (int i = n;i >= 1;i --)
		{
			nxtx1[i] = nxtx1[i + 1];
			if (a[nxtx1[i]] < a[i]) nxtx1[i] = i;
			nxtx2[i] = nxtx2[i + 1];
			if (a[nxtx2[i]] > a[i]) nxtx2[i] = i;
		}
		for (int i = 1;i <= m;i ++)
		{
			prey1[i] = prey1[i - 1];
			if (b[prey1[i]] < b[i]) prey1[i] = i;
			prey2[i] = prey2[i - 1];
			if (b[prey2[i]] > b[i]) prey2[i] = i;
		}
		for (int i = m;i >= 1;i --)
		{
			nxty1[i] = nxty1[i + 1];
			if (b[nxty1[i]] < b[i]) nxty1[i] = i;
			nxty2[i] = nxty2[i + 1];
			if (b[nxty2[i]] > b[i]) nxty2[i] = i;
		}
		if (a[prex2[n]] >= b[prey2[m]] || b[prey1[m]] <= a[prex1[n]]) return 0;
		return check1 (n , m) && check2 (1 , 1);
	}
}
int n , k , t;
void read (int &X)
{
	long long A;
	cin >> A;
	X = A;
}
signed main ()
{
	ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
	read (n) , read (k) , read (t);
	for (int i = 1;i <= n;i ++)
		read (x[i]);
	int l = 0 , r = 1e9 , mid;
	while (l < r)
	{
		mid = l + r >> 1;
		if (Check::check (k , n , t , mid)) r = mid;
		else l = mid + 1;
	}
	cout << (long long)r;
	return 0;
}

题解：AT_joisc2017_c 手持ち花火 (Sparklers)

文章操作

AT_joisc2017_c 手持ち花火

前言

正文

AC Code

相关推荐

评论

题解：AT_joisc2017_c 手持ち花火 (Sparklers)