80 lines
1.8 KiB
Markdown
80 lines
1.8 KiB
Markdown
# P16060 [CSPro 24] 序列查询新解 题解
|
||
|
||
## 75 pts 暴力
|
||
|
||
直接遵循题意使用 `lower_bound` 即可得到 75 pts
|
||
|
||
::::info[[75 pts 代码](https://www.luogu.com.cn/record/303048871)]
|
||
|
||
```cpp
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int n, N;
|
||
int a[100005];
|
||
int main() {
|
||
scanf("%d%d", &n, &N);
|
||
for (int i = 1; i <= n; ++i) {
|
||
scanf("%d", &a[i]);
|
||
}
|
||
long long ans = 0;
|
||
for (int i = 0; i <= N - 1; i++) {
|
||
int f = lower_bound(a, a + n + 1, i) - a;
|
||
while (a[f] <= i && f <= n)
|
||
f++;
|
||
f--;
|
||
int g = i / (N / (n + 1));
|
||
ans += abs(f - g);
|
||
}
|
||
printf("%lld\n", ans);
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
::::
|
||
|
||
## 100 pts 正解
|
||
|
||
注意到对于两个数 $a_i, a_{i + 1}$，$f(x) = i, x \in [a_i, a_{i + 1})$
|
||
|
||
且对于 $g$，只有 $i = k \times\frac{N}{(n + 1)}$ 的时候数值才会变化。
|
||
|
||
因此，统计 $f, g$ 分别变化的节点进行计算即可。
|
||
|
||
::::info[[100 pts 代码](https://www.luogu.com.cn/record/303064173)]
|
||
|
||
```cpp
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int n, N;
|
||
map<int, int> changes;
|
||
int main() {
|
||
scanf("%d%d", &n, &N);
|
||
for (int i = 1, a; i <= n; ++i)
|
||
scanf("%d", &a), changes[a] = 1;
|
||
for (int i = 1; i * (N / (n + 1)) < N; i++) {
|
||
if (changes.find(i * (N / (n + 1))) != changes.end())
|
||
changes[i * (N / (n + 1))] = 3;
|
||
else
|
||
changes[i * (N / (n + 1))] = 2;
|
||
}
|
||
changes[N] = 2;
|
||
int nowf = 0, nowg = 0;
|
||
long long ans = 0;
|
||
pair<int, int> pre = {0, 0};
|
||
for (pair<int, int> now : changes) {
|
||
ans += abs(nowg - nowf) * (now.first - pre.first);
|
||
if (now.second == 1)
|
||
nowf++;
|
||
else if (now.second == 2)
|
||
nowg++;
|
||
else
|
||
nowf++, nowg++;
|
||
pre = now;
|
||
}
|
||
printf("%lld\n", ans);
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
::::
|