修题面
- 板块P4272 [CTSC2009] 序列变换
- 楼主User_Unauthorized
- 当前回复1
- 已保存回复1
- 发布时间2024/1/2 20:20
- 上次更新2024/1/3 11:06:58
查看原帖
被骇客银狼阻止的越权访问保存失败
修题面
[CTSC2009] 序列变换
题目描述
给定一个整数序列 X1,X2,X3,...,Xn 和三个正整数 Q,A,B 满足：
-
1≤Xi≤Q 对于任意 1≤i≤n；
-
Xi≤Xi+1 对于任意 1≤i<n；
-
A≤n−1Q−1 且 A≤B。
对于任意 1≤i≤n，做如下变换：Yi=Xi+δi，其中 δi 是一个整数。使得新序列 Y 满足如下性质：
-
1≤Yi≤Q 对于任意 1≤i≤n；
-
Yi+1−Yi∈[A,B] 对于任意 1≤i<n。
对于这样一个变换，所需代价定义为 TransformCost(X,Y)=∑i=1n∣δi∣。
本题的任务即为寻找一个变换，使得 TransformCost(X,Y) 最小化。
输入格式
输入文件 sequence.in 包含两行。第一行 4 个整数，N,Q,A,B。接下来一行包含 N 个整数，分别为 X1,X2,X3,...,Xn。
输出格式
输出文件 sequence.out 仅包含一行，为最小的 TransformCost(X,Y)。
样例 #1
样例输入 #1
3 6 2 2
1 4 6
样例输出 #1
1
提示
样例说明
可以将序列变换为 2 4 6 或者 1 3 5。前者变换代价为 1，后者为 2。因此最小 TransformCost 为 1。
数据规模
对于 10%的数据 , N≤100,Q≤10000,1≤A,B≤100。
对于 30%的数据 , N≤10000,Q≤10000,1≤A,B≤100。
对于 60%的数据 , N≤10000,Q≤109,1≤A,B≤Q。
对于 100%的数据, N≤500000,Q≤109,1≤A,B≤Q。
# [CTSC2009] 序列变换
## 题目描述
给定一个整数序列 $X_1, X_2, X_3, ... ,X_n$ 和三个正整数 $Q, A, B$ 满足：
- $1 \leq X_i \leq Q$ 对于任意 $1 \leq i \leq n$；
- $X_i \leq X_{i+1}$ 对于任意 $1 \leq i < n$；
- $A \leq \frac{Q-1}{n-1}$ 且 $A \leq B$。
对于任意 $1 \leq i \leq n$，做如下变换：$Y_i = X_i + \delta_i$，其中 $\delta_i$ 是一个整数。使得新序列 $Y$ 满足如下性质：
- $1 \leq Y_i \leq Q$ 对于任意 $1 \leq i \leq n$；
- $Y_{i+1} - Y_i \in [A, B]$ 对于任意 $1 \leq i < n$。
对于这样一个变换，所需代价定义为 $\operatorname{TransformCost}(X, Y) = \sum_{i = 1}^{n}{\left\lvert\delta_i\right\rvert}$。
本题的任务即为寻找一个变换，使得 $\operatorname{TransformCost}(X, Y)$ 最小化。
## 输入格式
输入文件 sequence.in 包含两行。第一行 $4$ 个整数，$N, Q, A, B$。接下来一行包含 $N$ 个整数，分别为 $X_1, X_2, X_3, ... , X_n$。
## 输出格式
输出文件 sequence.out 仅包含一行，为最小的 $\operatorname{TransformCost}(X, Y)$。
## 提示
### 样例说明
可以将序列变换为 $2\ 4\ 6$ 或者 $1\ 3\ 5$。前者变换代价为 $1$，后者为 $2$。因此最小 $\operatorname{TransformCost}$ 为 $1$。
### 数据规模
对于 $10$%的数据 , $N \leq 100, Q \leq 10000, 1\leq A, B \leq 100$。
对于 $30$%的数据 , $N \leq 10000, Q \leq 10000, 1\leq A, B \leq 100$。
对于 $60$%的数据 , $N \leq 10000, Q \leq 10^9, 1\leq A, B \leq Q$。
对于 $100$%的数据, $N \leq 500000, Q \leq 10^9, 1\leq A, B \leq Q$。
加载中...