题解：P10806 [CEOI2024] 洒水器

题解区贪心题解看不明白啊。

Solution

先二分，最优性转可行性。判定是否可行。经典问题模型，左摆或右摆判断能否覆盖完整个区间。在经典模型中，每个花洒（或灯）的覆盖的长度可能不同。

这个经典问题的 dp 思路是，顺序考虑每个花洒（或灯），它向左扫能覆盖

[l,p_i]

，那么找到最小的

j

，使得前

j

个花洒能覆盖

[1,l)

，然后贪心地让

k\in (j,i)

的花洒

k

全部向右摆。对于每个花洒我们都只考虑它向左扫的贡献，因为它向右扫的贡献一定会在后面某一次向左扫的时候统计到（末尾特判一下）。

但这道题简单之处在于，所有花洒的覆盖范围是相同的，也即二分的

mid

。也就是说，上面的过程，

k\in (j,i)

的最优的

k

一定是

k=i-1

。

那么思路就很明了了。记

g_i

表示用前

i

个花洒最多能够覆盖编号

[1,g_i]

的花。注意，是连续覆盖，即全部覆盖了，没有空缺。转移分为两种。一种是直接贪心向左/右摆，如果前面

i-1

个花洒能够覆盖超过

s_i

，那

i

就可以贪心地向右摆，否则它必须向左摆，填满中间的空缺。这里填不满就报告不可行。另一种转移就是上面说的，让

i

向左摆，然后让

i-1

向右摆，此时调用

g_{i-2}

辅助转移即可。

复杂度

O(n\log^2n)

，但思路会比直接贪心来得更有道理一些？

Code

CPP

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)

const int maxn = 1e5 + 5;

int n, m, s[maxn], f[maxn];
int g[maxn], pre[maxn], nw[maxn], suf[maxn];
char Plan[maxn];

inline bool chck(int k){
	rep(i, 1, n) 
		suf[i] = upper_bound(f + 1, f + m + 1, s[i] + k) - f - 1;
		
	g[0] = 0;
	rep(i, 1, n) g[i] = pre[i] = 0;
	rep(i, 1, n){
		if(g[i - 1] == m){ g[i] = g[i - 1], pre[i] = -2; continue;} 
		if(f[g[i - 1] + 1] < s[i] - k) return 0;
		
		if(f[g[i - 1] + 1] < s[i]) g[i] = nw[i], pre[i] = -1;
		else g[i] = suf[i], pre[i] = -2;
		
		if(i > 1 and f[g[i - 2] + 1] >= s[i] - k){
			if(suf[i - 1] > g[i])
				g[i] = suf[i - 1], pre[i] = 1;
		}
	}
	
	if(g[n] < m) return 0; 
	
	int x = n;
	while(x){
		if(pre[x] < 0){
			if(pre[x] == -1) Plan[x] = 'L';
			else Plan[x] = 'R';
			--x;
		} else{
			Plan[x] = 'L', Plan[x - 1] = 'R';
			--x; --x;
		}
	}
	return 1;
}

int main(){
//	freopen("P10806_24.in", "r", stdin);
	
	ios_base::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	cin >> n >> m;
	rep(i, 1, n) cin >> s[i];
	rep(i, 1, m) cin >> f[i];
	
	if(n == 1){
		if(s[1] <= f[1]){
			cout << f[m] - s[1] << '\n';
			cout << "R" << '\n';
		} else if(s[1] >= f[m]){
			cout << s[1] - f[1] << '\n';
			cout << "L" << '\n';
		} else cout << -1 << '\n';
		return 0;
	}
	
	rep(i, 1, n)
		nw[i] = upper_bound(f + 1, f + m + 1, s[i]) - f - 1;

	int l = 0, r = 1e9, ans = -1;
	while(l <= r){
		int mid = l + r >> 1, tmp = chck(mid);
		if(tmp) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	
	cout << ans << '\n';
	rep(i, 1, n) cout << Plan[i]; cout << '\n';
	return 0;
}

题解：P10806 [CEOI2024] 洒水器

文章操作

Solution

Code

相关推荐

评论

题解：P10806 [CEOI2024] 洒水器