寒假集训Day3

今天主要讲了排序，下面放了一些遇到的比较好的题

种树

https://www.luogu.com.cn/problem/P1250
这道题用的是一个贪心
主要想法是，想要种的树尽量少，就要让重叠部分的树尽量多。重叠部分一定在结尾（我也没想明白为什么）
重点是重叠部分一定在结尾，虽然我也没想明白，但是我发现好像之前也遇到过关于区间的贪心按照结尾由小到大排序的，所以先这么记住，以后遇到类似的区间问题可以按照结尾由小到大排序
然后这道题排序完了之后从小到大扫描每一个结尾，然后种树就可以了

#include <bits/stdc++.h>
using namespace std;
struct tree{
	int	st,ed,v;
}a[100001];
int n,h;
int num = 0;
int pl[10000001] = { };
bool cmp(tree a,tree b) {
	return a.ed < b.ed;
}
int main () {
	scanf("%d %d" ,&n,&h);
	for(int i = 1;i <= h; i++) {
		scanf("%d %d %d" ,&a[i].st,&a[i].ed,&a[i].v);
	}
	sort(a + 1,a + 1 + h,cmp);
	for(int i = 1;i <= h; i++) {
		int k = 0;
		for(int j = a[i].st;j <= a[i].ed; j++) {
			if(pl[j] != 0) k++;
		}
		if(k >= a[i].v) continue;
		for(int j = a[i].ed;j >= a[i].st; j--) {
			if(pl[j] == 0) {
				pl[j] = 1;
				k++;
				num++;
				if(k == a[i].v) break;
			}
		}
	}
	printf("%d" ,num);
	return 0;
}

A-B数对

https://www.luogu.com.cn/problem/P1102
这道题C是定值，求A-B=C，可以转化一下，转化成A=B+C；
这里主要是想提一下lower_bound和upper_bound；
lower_bound(a + 1,a + 1 + n,c) - a返回的是在从1到n的范围内，数组a中第一个大于等于c的数的下标
upper_bound(a + 1,a + 1 + n,c) - a返回的是在从1到n的范围内，数组a中第一个大于c的数的下标
所以这道题可以从前到后遍历一遍，用Lower bound和upper bound找到a[i]+c（也就是B+C）的范围 然后二者做差就是要求的值

#include <bits/stdc++.h>
using namespace std;
long long n,c;
long long a[1000001] = { };
long long num = 0;
int main () {
	scanf("%lld %lld" ,&n,&c);
	for(int i = 1;i <= n; i++) {
		scanf("%lld" ,&a[i]);
	}
	sort(a + 1,a + 1 + n);
	for(int i = 1;i <= n; i++) {
		int x = upper_bound(a + 1,a + n + 1,a[i] + c) - a;
		int y = lower_bound(a + 1,a + n + 1,a[i] + c) - a;
		num += x - y;
	}
	printf("%lld" ,num);
	return 0;
}

导弹拦截

https://www.luogu.com.cn/problem/P1158
注意，这道题和那个最长单调序列的导弹拦截不一样。
按照题意，这道题我一开始想到的是构造两个雷达连线的中垂线，每个雷达只负责拦截自己一侧的导弹；
但是雷达不在坐标轴上，在程序里凭空画中垂线十分困难；
但是按照这样的想法继续看，就会发现我们需要的是找到那个临界雷达，让A覆盖住尽可能多，剩余的应该是离B比较近，交给B覆盖
那我首先让A覆盖住所有的导弹，然后让A放弃最远的导弹，交给B拦截；
然后让A再放弃一枚最远的导弹，把两颗导弹交给B，这时候B的范围就是这两颗中距离他最远的导弹；
以此类推……
所以我们首先可以把A雷达距离导弹的距离升序排列，然后再维护一个数组，这个数组的元素 a[i]表示的是，在a雷达放弃了(n-i)个导弹之后，由B雷达接手后B的覆盖范围
需要注意的是，a[n]=0,而存放A雷达的数组中，第0个元素也是0，模拟的分别是A和B完全放弃不管之后，覆盖全部导弹需要的代价

#include <bits/stdc++.h>
using namespace std;
int n;
int s1,s2;
int t1,t2;
struct d{
	int x;
	int y;
	int dis;
	int id;
}a[10000001];
int dis2[10000001] = { };
bool cmp(d m,d n) {
	return m.dis < n.dis;
}
int main () {
	scanf("%d %d %d %d" ,&s1,&t1,&s2,&t2);
	scanf("%d" ,&n);
	for(int i = 1;i <= n; i++) {
		scanf("%d %d" ,&a[i].x,&a[i].y);
		a[i].dis = pow(a[i].x - s1,2) + pow(a[i].y - t1,2);
		a[i].id = i;
	}
	a[0].dis = 0;
	sort(a + 1,a + 1 + n,cmp);
	dis2[n] = 0;
	for(int i = n - 1;i >= 0; i--) {
		int f = pow(a[i + 1].x - s2,2) + pow(a[i + 1].y - t2,2);
		dis2[i] = max(dis2[i + 1],f);
	}
	int ans = INT_MAX;
	for(int i = 0;i <= n; i++) {
		ans = min(ans,dis2[i] + a[i].dis);
	}
	printf("%d" ,ans);
	return 0;
}