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;
}