J - Symmetrical Painting
题意
给你(n)个矩形, 左下角((i-1, L_i))， 右上角((i, R_i)), 找一条线(l)平行于(x)轴， 让这些矩形根据(l)对称，不对称的部分删去，问最大的对称图形的面积是多少？
思路
主要就是要枚举对称轴啦，从小到大枚举(L_i、(L_i+R_i)/2、R_i)，这三种位置为对称轴。
那枚举的时候要怎么维护矩形面积。
- 首先可以把(L_i*2、R_i *2)，这样取中间不会出现误差。
- 然后分别标记三种位置为(1：L_i、 2:(L_i+R_i)/2、 3:R_i)
- 根据位置从小到大排序
- 用(a和b)标记加还是减， (ans):当前对称图形的面积
1、如果碰到标记(1， a++)
2、如果碰到标记(2， a--, b++)
3、如果碰到标记(3， b--)
(ans =ans + ( w_i - w_{i-1})*(a-b)*2)， 下面只针对一个矩形进行分析- (L_i le w_i le (L_i+R_i)/2)：对称面积变大， (ans =ans + ( w_i - w_{i-1})*2)
- ((L_i+R_i)/2le w_i le R_i)：对称面积变小， (ans =ans - ( w_i - w_{i-1})*2)， 因为之前加过((L_i+R_i)/2)~(L_i)的面积， 现在需要的面积是(w_i)~(R_i)的面积，那么就前面的减去(( w_i - w_{i-1})*2)
- (R_i le w_i)L：面积等于(0),再把(b--)就可以了。
- 最后的答案要记得(Max/2)
比赛的时候想的到枚举对称轴之类的，但是一直想不明白怎么维护，后来看到一些大佬的代码，简洁又巧妙。。。反正我想不出来。。继续努力吧。
代码
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 3e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
struct Node{
ll w;
int id;
bool operator < (Node const & a){
return w < a.w;
}
}node[maxn*4];
int main() {
scanf("%d", &n);
ll l, r;
int cnt = 0;
for(int i = 1; i <= n; i++){
scanf("%lld%lld", &l, &r);
l *= 2;
r *= 2;
node[++cnt] = {l, 1};
node[++cnt] = {(l+r)/2, 2};
node[++cnt] = {r, 3};
}
sort(node+1, node+cnt+1);
ll a = 0, b = 0, ans = 0, Max = 0;
for(int i = 1; i <= cnt; i++){
ans += (node[i].w - node[i-1].w)*(a-b)*2; \也可以这边不乘，最后就不用除了
if(node[i].id == 1)
a++;
if(node[i].id == 2){
a--;b++;
}
if(node[i].id == 3)
b--;
Max = max(Max, ans);
}
printf("%lld
", Max/2);
return 0;
}