专栏文章

题解：P12644 [KOI 2024 Round 1] 会议地点

lluoguzbh0011
P12644题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwo4k5
此快照首次捕获于
2025/12/02 09:34
3 个月前
此快照最后确认于
2025/12/02 09:34
3 个月前
查看原文
题目传送门。

思路：

首先想到直接暴力，时间复杂度 O(QN2⋅N!)O(QN^2 \cdot N!)。
所以，我们的目标是：把时间复杂度降到 O(Q)O(Q)，也就是单次询问时间复杂度 O(1)O(1)。

问题一：单次会议的开销

让我们看一个借来的公式：∑i=lr∣Xa−Xi∣\displaystyle\sum^{r}_{i = l}\vert X_a - X_i \vert。
如果去掉绝对值，想必大家都能成功化简，但问题是：怎么去掉绝对值。
注意到题面说“人家的坐标按从小到大的顺序排列”,所以上式可以被拆成两个部分：∑i=la−1(Xa−Xi)\displaystyle\sum^{a-1}_{i = l}(X_a - X_i) 和 ∑i=a+1r(Xi−Xa)\displaystyle\sum^{r}_{i = a+1}(X_i - X_a)。
化解得 (a−l)⋅Xa−∑i=la−1Xi+∑i=a+1rXi−(r−a)⋅Xa\displaystyle(a - l) \cdot X_a - \sum_{i=l}^{a-1}X_i + \sum_{i=a+1}^{r}X_i - (r - a) \cdot X_a。
求和部分可以用前缀和来做，整个式子时间复杂度 O(1)O(1)。
这样，时间复杂度就降为了 O(QN⋅N!)O(QN \cdot N!)。

问题二：会议的顺序

由于疲劳度关系到相邻的两个点，所以我们可以画图表示。
接下来我会用题面中的例子来做示范：
若会议召开顺序为 3→10→113 \rightarrow 10 \rightarrow 11，画图为：

这时我们注意到，这条线折返了一下，这个折返是无用的。
怎么让它不折返呢？我们只需要使召开顺序从小到大或从大到小排序就行了。
像这样：

这样我们就不用枚举所有排序了，时间复杂度 O(QN)O(QN)。

问题三：计算最小疲劳度

观察问题二中的图，我们发现一次会议集合的最小疲劳度是最大开销减最小开销。
那如何计算最大开销与最小开销呢？
对于一个下标为 aa 的开会地点，设其右边有 xx 户人家，左边有 yy 户人家，向右移动一户人家会移动 uu 个单位，向左移动一户人家会移动 vv 个单位。
aa 每向右移动一次，开销会增加 (x−1−y)⋅u(x - 1 - y) \cdot u,
aa 每向左移动一次，开销会增加 (y−1−x)⋅u(y - 1 - x) \cdot u。
随便选一个点，每次在下面三种行动方案中选一种开销最小的一种执行，观察 aa 的变化。
  • 不动。
  • 向左移动一次。
  • 向右移动一次。
我们发现，aa 最后总是会停在正中间，这就证明，在正中间的人家开会，开销最小。
再做类似的实验，不过，这次找开销最大的人家。
我们又发现，aa 最后总是会停在最外侧，这就证明，在最外侧的人家开会，开销最大。
这样我们就可以只计算三户人家了，时间复杂度终于来到了 O(Q)O(Q)。

代码

给代码之前，还有一件事要说：题面读入的是坐标，我们要的是下标，所以我们要二分查找下标。
上代码：
CPP
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
long long n,z[200009],q,h[200009],l,r;//不开 long long 见祖宗
long long hy(long long a){
	return (z[a]*(a-l)-(h[a-1]-h[l-1]))+((h[r]-h[a])-z[a]*(r-a));
}
int main(){
	cin>>n>>q;
	FOR(i,1,n){
		cin>>z[i];
		h[i]=h[i-1]+z[i];
	}
	while(q--){
		int x,y;
		cin>>x>>y;
		l=lower_bound(z+1,z+1+n,x)-z;   //lower_bound找第一个大于等于x的数，返回地址，-z获得下标
		r=upper_bound(z+1,z+1+n,y)-z-1; //upper_bound找第一个大于x的数，-1后就是最后一个小于等于x的数
		if(l<=0||l>n||r<=0||r>n||l>=r){ //一定要有，判断区间里是否有人家
			cout<<"0\n";
			continue;
		}
		long long maxx=max(hy(l),hy(r));
		long long minn=hy(l+(r-l)/2);
		cout<<maxx-minn<<"\n";
	}
}
看在我写了三个小时的份上，点个赞再走呗！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...