P10224 [COCI 2023/2024 #3] Vrsar 题解

知识点

前缀和思想，贪心。

题意分析

我觉得题目挺清晰了……

思路

部分分

没必要，OK？

我不会告诉你我考场上打部分分打了 30 min，还只有 8 分。

正解

我们设一个方案 \(S\) 为 \(\{ x_1,x_2...x_n \}\)，其中 \(x_i\) 表示第 \(i\) 个滑雪场的数轴坐标，\(T\) 为该方案的可能最大滑雪时间。

思考一下：如果我们不考虑下山的时间，那么对于一个方案 \(S\)，我们去掉其中不为 \(x_n\) 的任意一个滑雪场，形成一个新的方案 \(S'\)，该方案的可能最大滑雪时间 \(T'\) 必定等于 \(T\)。

而当我们考虑下山的时间，那么对于一个方案 \(S\)，我们去掉其中不为 \(x_n\) 的任意一个滑雪场，形成一个新的方案 \(S'\)，通过上面的推导，该方案的可能最大滑雪时间 \(T'\) 必定大于等于 \(T\)，因为我们少去一个滑雪场，就少一次下山的时间，可以省出更多时间滑雪。

那我们就可以直接到某一个滑雪场即可。

现在算一下代价：设起点数轴坐标为 \(x\)，终点滑雪场数轴坐标为 \(y\)，关闭时间为 \(t\)，那么最长时间为 \(\max{(0,t-|x-y|)}\)，我们可以分类讨论再拆开（套路），用前缀和处理一下即可。

CODE

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e5+10;
int n,m;
int b[N];
ll l[N],r[N];
struct node{
	ll x,t;
	friend bool operator <(node a,node b){
		return a.x<b.x;
	}
}a[N];
signed main(){
	cin>>n>>m;
	RCL(l,-0x3f,l,1),RCL(r,-0x3f,r,1);
	FOR(i,1,n){
		int x;
		cin>>a[i].x>>a[i].t>>x;
	}
	sort(a+1,a+n+1);
	FOR(i,1,n)b[i]=a[i].x;
	FOR(i,1,n)l[i]=max(l[i-1],a[i].t+a[i].x);
	DOR(i,n,1)r[i]=max(r[i+1],a[i].t-a[i].x);
	while(m--){
		int x;cin>>x;
		int tot=lower_bound(b+1,b+n+1,x)-b,ans=max(l[tot-1]-x,r[tot]+x);
		cout<<ans<<' ';
	}cout<<endl;
	return 0;
}