洛谷 P6515 【[QkOI#R1] Quark and Game】题解

我们将所有二元组看成平面直角坐标系上的点

我们可以分别将操作看成翻转空间和砍掉平面上的点，那么我们其实就是在看最小花费多少可以使所有点被砍掉

我们可以发现，整个操作就是在不断缩小能容纳点的空间的范围，而这个空间就是两条过原点的直线的夹角，因此我们只需要保证这两条直线的夹角在相邻两点与原点的夹角的中间即可

首先对所有点进行极角排序，先特判一下两条直线都在所有向量的直线的一侧，然后我们就可以对任意两个相邻向量进项考虑，对于每两个相邻向量都有以下情况：

1.当a，b均在直线y=x下时，应当进行操作2，若进行操作1，那么a，b将同时变得不可操作，此时漏掉向量的区域就会在它们上方。

2.当 a，b均在直线y=x上时，应当进行操作1，若进行操作2，那就又回到了情况 1，但是情况 1 又只能再翻回来，且进行操作1也缩小了夹角大小并不会使得有点被漏掉。

3.当a，b一个在y=x上，一个在下时，只要进行操作1，那么就会使一个向量变得不可操作，然后再进行一次操作2再一直进行操作直到另一个向量不可操作即可。此外我们需要比较一下是否需要先进行一次操作2使得花费更小

对于所有方案的最小值即为答案。由于情况3只会出现一次，情况1，2本质上就是辗转相除法，因此复杂度为O(n log min(a, b))

code:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

int n, p, q;

ll ans;

struct node

{

    int x;

    int y;

} c[100005];

bool cmp(node aa, node bb)

{

    return (ll)aa.x * bb.y > (ll)aa.y * bb.x;

}

int main()

{

    scanf("%d%d%d", &n, &p, &q);

    for (int i = 1; i <= n; ++i)

        scanf("%d%d", &c[i].x, &c[i].y);

    sort(c + 1, c + n + 1, cmp);

    ans = min((ll)ceil((double)c[n].y / c[n].x) * p, (ll)ceil((double)c[1].x / c[1].y) * p + q);

    for (int i = 1; i < n; ++i)

    {

        node u = c[i], v = c[i + 1];

        if (u.x * v.y == u.y * v.x)

            continue;

        ll num = 0;

        while (true)

        {

            if (u.x >= u.y && v.x >= v.y)

            {

                swap(u.x, u.y);

                swap(v.x, v.y);

                num += q;

            }

            else if (u.x < u.y && v.x < v.y)

            {

                int cnt = min((u.y - 1) / u.x, (v.y - 1) / v.x);

                u.y -= cnt * u.x;

                v.y -= cnt * v.x;

                num += (ll)cnt * p;

            }

            else

            {

                if (u.x >= u.y)

                    swap(u, v);

                ll tmp = 0;

                node w = u;

                w.y -= w.x;

                tmp = p + q + (ll)ceil((double)w.x / w.y) * p;

                if (v.x != v.y)

                {

                    w = v;

                    swap(w.x, w.y);

                    w.y -= w.x;

                    tmp = min(tmp, p + 2 * q + (ll)ceil((double)w.x / w.y) * p);

                }

                num += tmp;

                break;

            }

        }

        ans = min(ans, num);

    }

    printf("%lld", ans);

    return 0;

}