传送门：https://codeforces.com/gym/102483/problem/A
题意
给出n个点的$a（x_i,y_i）$，然后在二维平面中构造n个点，构造的点可以重合。 构造点的要求为：若为第i和第j个点，$（i<j）$，则$(x_i<=x_j，y_i<=y_j)$ 贡献为$\sum_{i=1}^np_i-a_i^2$，求最小贡献。
思路
先将题面转化一下为:$\sum_{i=1}^n(p_{ix}-a_{i_x})^2+(p_{iy}-a_{i_y})^2$
看到x和y是相互独立的，所以只需要写出一个函数，然后在套一个即可。
根据题意，我们构造的p在[1,n]上要是单调递增的。 $那么怎么求最小的\sum_{i=1}^n(p_{ix}-a_{ix})^2？$
分析以下几种情况：
- a是单调递增的，那根本不用想，让$p_{ix}=a_{ix}$，答案为0.
- a全为一个数，那p也为a的平均值，答案也为0.
- a是不递增的，这是本题的关键，因为p是递增的，如果a越来越小，而p越来越大，那该怎么构造呢？
当a是单调递增的时候，非常好构造所以我们不让a有递减的部分，也就是把任意形式的a都转化为单调递增。
我们对于a中一段的串，取一个平均值，再处理下一个串，使当前串的平均值要大于上一个串的平均值，我们要做到将一段长度的平均值递增即可。
问题：怎么维护一段长度平均值递增？
回答：暴力$O(n^2) No$，单调栈即可。
我们用单调栈维护一段串的平均值递增即可，因为x和y独立，所以y也是如此。
Code（62MS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| ##include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
const int N = 1e6 + 10;
ll x[N], y[N];
int n;
double sum(ll *A, int n) {
stack<pair<ll, int> > s;
double ans = 0;
for(int i = 1;i <= n; i++) {
ll a = A[i]; int l = 1;
while(!s.empty() && s.top().first * l >= s.top().second * a) {
l += s.top().second;
a += s.top().first;
s.pop();
}
s.push({a, l});
}
int i = n;
while(!s.empty()) {
double tmp = 1.0 * s.top().first / s.top().second;
int l = s.top().second;
s.pop();
for(int j = 0;j < l; j++) {
ans += (tmp - A[i - j]) * (tmp - A[i - j]);
}
i -= l;
}
return ans;
}
void solve() {
scanf("%d",&n);
for(int i = 1;i <= n; i++) {
scanf("%lld%lld",&x[i], &y[i]);
}
printf("%lf\n" ,sum(x, n) + sum(y, n));
}
int main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/06/2018-2019-icpc-nwerc-2018-a/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！