ζ

算法竞赛进阶指南-0x06-Genius ACM

    题解

题目链接

首先需要解决的问题是：如何求给定集合的校验值？

对于给定的集合S，为了使它的校验值最大，用来求它校验值的数值之间的差当然也要尽可能地大，所以用于求校验值的2M个数肯定就是集合中最大地M个数和最小的M个数。

接下来就是它们之间如何配对的问题。有四个数a<b<c<da<b<c<d，它们之间一共有3种配对方法，其中{a,b},{c,d}\{a,b\},\{c,d\}的配对方法差显然不够大，于是就变成了比较下面两种配对方法的校验值大小

{a,c},{b,d}{a,d},{b,c}\{a,c\},\{b,d\} \\ \{a,d\},\{b,c\}

也就是比较这两个值的大小

(c−a)2+(d−b)2(d−a)2+(c−b)2(c-a)^2+(d-b)^2 \\ (d-a)^2+(c-b)^2

展开，

a2+b2+c2+d2−2ac−2bda2+b2+c2+d2−2ad−2bca^2+b^2+c^2+d^2-2ac-2bd \\ a^2+b^2+c^2+d^2-2ad-2bc

两式同时减去a2+b2+c2+d2a^2+b^2+c^2+d^2，

−2ac−2bd−2ad−2bc-2ac-2bd \\ -2ad-2bc

两式同时除以2，

−ac−bd−ad−bc-ac-bd \\ -ad-bc

两式同时加上ac+bcac+bc，

bc−bdac−adbc-bd \\ ac-ad

提取公因式得

b(c−d)a(c−d)b(c-d) \\ a(c-d)

由b>ab>a，且c<d=>c−d<0c<d=>c-d<0，上式永远不大于下式，所以选{a,d},{b,c}\{a,d\},\{b,c\}这种分法。

推广到整个问题空间，也就是要将集合最大的数与最小的数配对，次大的数与次大的数配对，以此类推。

若想使序列最终分成的段数尽可能少，自然要使每一段在校验值不大于T的条件下尽可能地长。起点相同的段，终点距离起点更远的段的校验值总是不小于距离起点更近的段的校验值，所以可以用二分答案之类的方法来找到能取得的最大段。但这道题卡了二分，有的数据的段都只能取很小，而用二分的话需要先验证大段不行才能一步步往小了取。这里就用到了倍增来查找。

这题的时间卡得非常紧，找区间内最大/最小数配对时不能直接对区间sort。在倍增期间，待求的区间的左半边总是有序的，将它与待求区间右边归并排序可以有更高效率。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
long long a[500005], k;
int n, m;
bool C(int hd, int l, int dis)
{
    int i;
    vector<long long> pq;
    for (i = 1; i <= dis; i++)
        pq.push_back(a[i + l]);
    sort(pq.begin(), pq.end());
    long long ret = 0;
    int sum = 0, j = 0;
    vector<long long> t;
    i = hd;
    while (i <= l && j < pq.size())
    {
        if (pq[j] > a[i])
            t.push_back(a[i++]);
        else
            t.push_back(pq[j++]);
    }
    while (i <= l)
        t.push_back(a[i++]);
    while (j < pq.size())
        t.push_back(pq[j++]);
    j = t.size() - 1;
    i = 0;
    while (j > i && sum < m)
    {
        ret += (t[i] - t[j]) * (t[i] - t[j]);
        i++;
        j--;
        sum++;
    }
    return ret <= k;
}
int main()
{
    int _, i;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%d%d%lld", &n, &m, &k);
        for (i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        int l = 1, dis, res = 0, hd = 1;
        while (hd <= n)
        {
            dis = 1;
            while (l + dis <= n && C(hd, l, dis))
                dis <<= 1;
            dis >>= 1;
            if (dis == 0)
            {
                res++;
                l++;
                hd = l;
                continue;
            }
            vector<long long> pq;
            for (i = 1; i <= dis; i++)
                pq.push_back(a[i + l]);
            sort(pq.begin(), pq.end());
            long long ret = 0;
            int sum = 0, j = 0;
            vector<long long> t;
            i = hd;
            while (i <= l && j < pq.size())
            {
                if (pq[j] > a[i])
                    t.push_back(a[i++]);
                else
                    t.push_back(pq[j++]);
            }
            while (i <= l)
                t.push_back(a[i++]);
            while (j < pq.size())
                t.push_back(pq[j++]);
            for (i = 0; i < t.size(); i++)
                a[hd + i] = t[i];
            l += dis;
        }
        printf("%d\n", res);
    }
    return 0;
}
页阅读量:  ・  站访问量:  ・  站访客数: