| by XianKa | No comments

【19牛客多校9_J】Symmetrical Painting【另类扫描线】

传送门

题意是说给n<=3e5条宽度为1的线段,长度不定。

要求一个对称轴,使得将图按照对称轴处理以后剩下的线段最多。

首先猜到的就是对称轴必定出现在某个线段的正中央。但是枚举对称轴以后需要用数据结构维护两边的长度。

有一种离线的做法,更为简单。

  1. 预处理出每条线的 下边线(l)、中线(l+r>>1)、上边线(r)。

  2. 对于这些预处理出的线,仅仅记录一个y坐标,按照坐标从小到大排序。

  3. 枚举这些线当作对称轴,从下往上做扫描线。线性讨论当前这条线和上一条线之间的线段产生的贡献。也就是当前线为对称轴,上一条线为下半段。按照扫描线一层一层的计算面积贡献。

  4. 在某个线段遇到中线之前,他的面积贡献都是存在的。因为他按照当前扫描线往上翻折,扫描线下方的面积肯定小 于上方,所以贡献是下方面积的两倍 ,于是下边界的贡献flag = 1。

  5. 当扫描线遇到中线的时候,肯定是之前某个线段的中线,此时这条线段在扫描线下方的面积大于等于上方面积,同时这条线段已经达到最大的面积贡献,当扫描线再往上走的时候会减少贡献,每当中线网上移动距离 k 的时候,这条线段就应该减去 2k 的面积贡献。当遇到上边界的时候负贡献消失,变成 0 贡献。于是中线的贡献flag = -2,上边界的flag = 1。

  6. 所以用变量cnt对当前层做出贡献的线段条数,面积和sum每次都+=cnt*(i-last)。然后cnt+=当前层数的贡献。因为兑成轴的只可能产生0.5这种小数,于是为了代码方便,把坐标都扩大两倍,同时计算面积的时候不用乘2。


其实最核心的点就是每当对称轴向上移动k距离的时候,整条线就应该缩短2k的距离,这样才能保证图形是对称的。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 233;
int n;
vector<pii> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        a.push_back({l * 2, 1});
        a.push_back({l + r, -2});
        a.push_back({r * 2, 1});
    }
    sort(a.begin(), a.end());
    ll ans = 0, last = 0, cnt = 0, sum = 0;
    for(auto &x: a)
    {
        sum += cnt * (x.first - last);
        last = x.first;
        ans = max(ans, sum);
        cnt += x.second;
    }
    cout << ans << endl;
}

发表评论