UVALive 7261 Xiongnu's Land【差分】

淩亂°似流年 2023-06-01 06:20 11阅读 0赞

题目链接：[https://vjudge.net/problem/UVALive-7271][https_vjudge.net_problem_UVALive-7271]

题意：给你一个n\*n的矩形区域，左下角是（0,0），然后给你m个区域内的小矩形，然后让你从某个竖线划分开，使得

1.左边小矩形总面积大于等于右边的，并且使差值尽可能小。

2.在满足条件1的情况下使得竖线尽可能往右。

思路：我们假设在x处分开，然后我们考虑如果在x+1处分开会有什么影响，根据差分的思想，或者说是扫描线？每个小矩形对这段区间的贡献，差分一下，然后求个前缀和就是竖线右移会产生的影响，我们就从0枚举到n就可以找到最优解了。

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e6 + 10;
    const ll inf = 0x3f3f3f3f3f3f3f3f;
    ll a[maxn];
    struct node
    {
        int x, y, w, h;
    }b[maxn];
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            int n, m;
            scanf("%d%d", &n, &m);
            memset(a, 0, (n + 1) * sizeof(ll));
            ll sum = 0;
            for(int i = 1; i <= m; ++i)
            {
                scanf("%d%d%d%d", &b[i].x, &b[i].y, &b[i].w, &b[i].h);
                a[b[i].x + 1] += b[i].h, a[b[i].x + b[i].w + 1] -= b[i].h;
                sum += 1ll * b[i].w * b[i].h;
            }
            for(int i = 1; i <= n; ++i)
                a[i] += a[i - 1];
            int ans = 0;
            ll res = 0, Min = inf;
    
            for(int i = 0; i <= n; ++i)
            {
                res += a[i];
                if(res * 2 >= sum && Min >= res)
                {
                    Min = res;
                    ans = i;
                }
            }
            printf("%d\n", ans);
        }
        return 0;
    }

[https_vjudge.net_problem_UVALive-7271]: https://vjudge.net/problem/UVALive-7271