题目链接：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; }
