CSP/信奥赛C++刷题训练：经典差分例题（3）：洛谷P5542 ：[USACO19FEB] Painting The Barn S

CSP/信奥赛C++刷题训练：经典差分例题（3）：洛谷P5542 ：[USACO19FEB] Painting The Barn S

题目描述

农夫约翰不擅长多任务处理。他经常分心，很难完成长的项目。目前，他正试图在谷仓的一侧上漆，但他一直在画小矩形区域，然后由于照料奶牛的需要而偏离了方向，使得谷仓的某些部分上漆的涂料比其他部分多。

我们可以将谷仓的一侧描述为一个二维 $x-y$ 平面，农夫约翰在该平面上绘制 $n$ 个矩形，每个矩形的边都与坐标轴平行，每个矩形由谷仓的左下角和右上角点的坐标描述。

农夫约翰想在谷仓上涂几层油漆，这样在不久的将来就不需要再重新粉刷了。但是，他不想浪费时间涂太多的油漆。结果表明，$K$ 涂层是最佳用量。请在他画完所有的长方形后，帮他确定谷仓有多少面积被 $K$ 层油漆覆盖。

输入格式

输入的第一行包含 $n$ 和 $K$。

其余 $n$ 行中的每一行包含四个整数 $x1$、$y1$、$x2$、$y2$，描述正在绘制的矩形区域，左下角 $(x1,y1)$ 和右上角 $(x2,y2)$。所有 $x$ 和 $y$ 值都在 $0$ 到 $1000$ 范围内，并且所有矩形都有正面积。

输出格式

请输出谷仓被 $K$ 层油漆覆盖的区域。

样例 #1

样例输入 #1

3 2
1 1 5 5
4 4 7 6
3 3 8 7

样例输出 #1

8

提示

$1\le K\le n\le 10^5$。

USACO 2019 二月月赛银牌组第二题。

使用差分解题

#include<bits/stdc++.h>
using namespace std;
//差分：c[i][j]=a[i][j]-a[i][j-1] 
int n,k,a1,b1,a2,b2,cnt=0; 
int a[1010][1010];//标记数组
int c[1010][1010];//差分数组 
int main(){
	cin>>n>>k;
	while(n--){
		cin>>a1>>b1>>a2>>b2;//左下（a1,b1),右上(a2,b2) 
		for(int i=a1;i<a2;i++){//右上不标记
			c[i][b1]++;
			c[i][b2]--;
		}
	}
	for(int i=0;i<=1000;i++){
		for(int j=0;j<=1000;j++){
			a[i][j]=c[i][j]+a[i][j-1];
		}	
	} 
	for(int i=0;i<=1000;i++){
		for(int j=0;j<=1000;j++){
			if(a[i][j]==k) cnt++; 
		}
	} 
	cout<<cnt;
	return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容