P11335题解

科技：

set

思路：

考虑可以用一只手，先按按钮

i

再按按钮

j

的条件：

\begin{cases}T_i\le T_j\\|A_i-A_j|\le T_j-T_i\end{cases}

发现二式成立时一式显然成立。将绝对值拆开，得：

\begin{cases}A_i+T_i\le A_j+T_j\\T_i-A_i\le T_j-A_j \end{cases}

那么原问题等价于将原序列拆成尽量少的子序列，使得每个子序列中的元素都二位偏序地上升。
设

x_i=A_i+T_i,y_i=T_i-A_i

，然后把所有元素按

x

排序，从小到大枚举，并维护所有的子序列。
当我们枚举到

i

时，如果此时所有子序列末尾一项的

y_j

都大于

y_i

，那么我们必须新开一个子序列；
否则，找到所有满足

y_j\le y_i

的子序列中

y_j

最大的一个，然后将

i

加入该子序列中。
考虑正确性：不难发现我们只关心子序列个数以及它们末尾项的

y_j

（越小越好）。无论我们选择哪个

j

进行操作，最终都会变成

y_i

，而其余的

y_j

不变。而由于我们选择了

y_j

最大的一个进行操作，所以剩下的

y_j

肯定是更小的，因此这样操作一定是最优的。
于是我们可以用一个 set 维护所有子序列的末尾项，以便插入、删除、查前驱这些操作，时间复杂度单

\log

。

代码：

CPP

#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int N = 5e5 + 5;
int n,m,a[N],t[N];
pii p[N];
set <int> s;
set <int> :: iterator it;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++) scanf("%d",&t[i]);
	for(int i = 1;i <= m;i++) scanf("%d",&a[i]);
	for(int i = 1;i <= m;i++) p[i] = mkp(a[i] + t[i],t[i] - a[i]);
	sort(p + 1,p + m + 1);
	for(int i = 1;i <= m;i++)
	{
		if(!s.empty() && (*s.begin()) <= p[i].se)
		{
			it = s.upper_bound(p[i].se),it--;
			s.erase(it);
		}
		s.insert(p[i].se);
	}
	printf("%d\n",(int)s.size());
	return 0;
}

文章操作

科技：

思路：

代码：

相关推荐

评论

P11335题解