【洛谷6936】[ICPC2017 WF] Scenery(思维)

点此看题面

  • 要拍\(n\)张照片,第\(i\)张照片可以拍摄的时间区间为\([l_i,r_i]\)。
  • 拍任意一张照片都需要连续\(m\)的时间,问是否能拍出所有照片。
  • \(n\le10^4\)

一个错误贪心及卡法

很容易想到一个错误的贪心,就是每次在能拍的范围内选取\(r_i\)最小的拍掉。

但这是很容易卡掉的,只要给一个大区间\([L,R]\)包含一个小区间\([l,r]\),我们会优先选择\([L,R]\),那么拍完之后时间已经达到了\(L+m\),只要让\(r-l\ge m\)且\(r-(L+m)<m\),就构造出了一种有解会被判成无解的情况。

把这种卡法扩展到更一般的情况,就发现对于任意若干张照片,假设最早可以从\(A\)时刻开始拍,最迟需要从\(B\)时刻开始拍,则\((B-m,A)\)这段时间中就不允许拍任何照片。

非法区间

我们把不允许拍任何照片的时段称为非法区间。

考虑一个区间\([L,R]\)包含的全部区间,我们无视限制从后往前贪心搞,就可以求出最迟的开始时刻\(K\),根据前面的结论,\((K-m,L)\)就是一个非法区间。

那么我们从大到小枚举\(L\),保证之前确定的非法区间不被选择,如果出现无解就无解,如果到最后都没有无解就有解(因为我们相当于已经构造出了一个方案)。

代码:\(O(n^2)\)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 10000
using namespace std;
int n,m,f[N+5],g[N+5],p[N+5],R[N+5];
struct Il {int l,r;I bool operator < (Con Il& o) Con {return l^o.l?l<o.l:r<o.r;}}s[N+5];
int main()
{
	RI i,j;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d%d",&s[i].l,&s[i].r),R[i]=s[i].r;
	for(sort(s+1,s+n+1),sort(R+1,R+n+1),i=1;i<=n;++i) f[i]=R[i],g[i]=s[i].l,p[i]=n;//区间排序;右端点排序;初始化信息
	for(i=n;i;--i) for(j=n;R[j]>=s[i].r;--j) {f[j]-=m;//从大到小枚举i;将j大于等于区间右端点的f[j]减去m
		W(p[j]^i&&f[j]<s[p[j]].l) f[j]=min(f[j],g[p[j]--]);if(f[j]<s[i].l) return puts("no"),0;g[i]=min(g[i],f[j]-m);}//非法区间不能选择;将i的非法区间端点取min
	return puts("yes"),0;
}
上一篇:springboot + neo4j 图形数据库 整合(本地)


下一篇:Asp.net Web.Config - 配置元素 httpCookies