P1083 [NOIP2012 提高组] 借教室

Label

简单的二分答案+简单差分数组维护

Description

https://www.luogu.com.cn/problem/P1083

Solution

解法一—线段树

维护区间 r r r数组最小值,每一个订单相当于区间减 d i d_i di​,若某个订单对应的操作使得全局最小值小于 0 0 0,则答案即为该份订单,否则输出0。

解法二—二分答案

此题单调性:订单越多,该订单越有可能无法被满足。

一般来说,二分是个很有用的优化途径,而对于能否二分,有一个界定标准:状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。 对于此题,如果前一份订单都不满足,那么之后的所有订单都不用继续考虑;而如果后一份订单都满足,那么之前的所有订单一定都可以满足,符合局部舍弃性,所以可以二分订单数量。所以,根据这两个性质,对于此题,我们二分检查 k k k份订单是否可被满足。

问题来了,对于每一个答案 k k k,如何检查 k k k份订单是否可被满足?

我们易知:对于每一个订单 ( d i , s i , t i ) (d_i,s_i,t_i) (di​,si​,ti​),相当于使 r s i ∼ r t i r_{s_i}\sim r_{t_i} rsi​​∼rti​​ 全部减去 t i t_i ti​。当对前 i i i组订单执行完此操作后,我们查看所有 r i r_i ri​,若无小于0的值则 i i i份订单是否可被满足,否则不可被满足。这个操作我们可以用线段树维护(但这样一来直接用解法一做即可,不可取),但我们有更加简便的操作—差分数组。

差分数组支持 O ( 1 ) O(1) O(1)的区间加/减与 O ( n ) O(n) O(n)的单值查询,对于此题,我们设 d i f [ i ] = r [ i ] − r [ i − 1 ] dif[i]=r[i]-r[i-1] dif[i]=r[i]−r[i−1],对于每组订单 ( d i , s i , t i ) (d_i,s_i,t_i) (di​,si​,ti​),令 d i f [ s [ i ] ] − = d [ i ] , dif[s[i]]-=d[i], dif[s[i]]−=d[i], d i f [ t [ i ] + 1 ] + = d [ i ] dif[t[i]+1]+=d[i] dif[t[i]+1]+=d[i];修改完后的 r i = ∑ k = 1 i d i f [ k ] r_i=\sum_{k=1}^{i}dif[k] ri​=∑k=1i​dif[k],检查其中是否存在大于0的情况即可。

算法复杂度: O ( n l o g n ) O(nlogn) O(nlogn)

最后注意:由于我们实际二分出来的值是“可满足的订单的最大值”,故边界情况需要特判(对于二分答案,任何时候认真考虑上下边界的取值都是必要的)。

Code

#include<cstdio>
#include<iostream>
#define ri register int
using namespace std;

const int MAXN=1e6+20;
int N,M,a[MAXN],d[MAXN],s[MAXN],t[MAXN],l,r,mid,dif[MAXN],ans;

bool check(int sj)
{
	for(ri i=1;i<=N;++i)	
		dif[i]=a[i]-a[i-1];
	for(ri i=1;i<=sj;++i)
	{
		dif[s[i]]-=d[i];
		dif[t[i]+1]+=d[i];
	}
	for(ri i=1;i<=N;++i)
	{
		dif[i]=dif[i-1]+dif[i];
		if(dif[i]<0)	return false;
	}
	return true;
}

int main()
{
	scanf("%d%d",&N,&M);
	for(ri i=1;i<=N;++i) scanf("%d",&a[i]);
	for(ri i=1;i<=M;++i) scanf("%d%d%d",&d[i],&s[i],&t[i]);
	l=1,r=N;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(check(mid))	l=mid;
		else	r=mid-1;
	}
	if(l==1)
	{
		if(check(l))	ans=2;
		else ans=1;
	}
	else if(l==N)
	{
		if(check(l))	ans=N+1;
		else	ans=N;
	}
	else ans=l+1;
	if(ans>N)	cout<<"0";
	else	cout<<"-1"<<'\n'<<ans;
	return 0;
}
上一篇:[NOIP2012 提高组] 疫情控制


下一篇:【NOIP2012提高组】疫情控制