Samurai's Stroke

题意：

一个长度为L的木棍，有n个支点支撑，每一个点是一个int数。表示距离木棍左端点的距离。求在那些位置将木棍劈开能够使得至少有一个木棍掉下去，输出这些位置的长度

3 ≤ l ≤
109;
2 ≤ n ≤ 105
分析：

对于左端的木棍。假设会掉下去一定是重心在木棍之外。两种情况：1，在最左端木棍之外。2，在最右木棍之外

每次能够得到一个答案区间，最后再从右向左处理一下，将区间合并即答案

const int maxn = 1100000;

struct Seg

{

    int l, r;

    bool operator< (const Seg& rhs) const

    {

        if (l != rhs.l)

            return l < rhs.l;

        return r < rhs.r;

    }

} x[maxn];

int tot, L, n;

int ipt[maxn];

void fun(bool flag)

{

    if (flag)

        x[tot++] = (Seg){ L - 2 * ipt[0], L };

    else

        x[tot++] = (Seg){ 0, 2 * ipt[0] };

    REP(i, n - 1)

    {

        int l = ipt[i] * 2, r = ipt[i + 1];

        if (l <= r)

        {

            if (flag)

                x[tot++] = (Seg){ L - r, L - l };

            else

                x[tot++] = (Seg){ l, r };

        }

    }

}

int main()

{

    while (~RII(L, n))

    {

        tot = 0;

        REP(i, n)

            RI(ipt[i]);

        sort(ipt, ipt + n);

        fun(false);

        REP(i, n)

            ipt[i] = L - ipt[i];

        sort(ipt, ipt + n);

        fun(true);

        sort(x, x + tot);

        int cnt = 1;

        FF(i, 1, tot)

        {

            int &l1 = x[cnt - 1].l, &r1 = x[cnt - 1].r;

            int &l2 = x[i].l, &r2 = x[i].r;

            if (r1 >= l2)

            {

                r1 = max(r1, r2);

            }

            else

            {

                x[cnt].l = l2;

                x[cnt].r = r2;

                cnt++;

            }

        }

        tot = cnt;

        int ans = 0;

        REP(i, tot)

        {

            ans += x[i].r - x[i].l;

        }

        WI(ans);

    }

    return 0;

}

巴特西

Samurai's Stroke

最新文章

热门文章

巴特西

Samurai&#39;s Stroke

最新文章

热门文章

Samurai's Stroke