2022杭电多校3

题意：给定n和k，n代表快递个数，k代表一次最多能拿的快递数，接下来n行每行给出两个数，分别代表快递的到达时间以及截至时间，我们必须要在截止时间之前把快递取走，一天可以取多次快递，问我们取完所有的快递至少需要取的次数。

iidea：我们可以尽量把取快递的时间往后延，这样我们相应地一次取出来的快递数也可能会更多，我们只在截至时间取快递，我们一次尽可能地多取快递，首先我们需要先对所有的快递按照开始时间 l l l从小到大排序，然后遍历一遍，我们可以设置一个时间t代表我们当前的时间点，我们用一个队列记录当前时间已经到达且还未取出的快递，则所有 l < t l

当t到达一个快递的结束时间时队列中的快递数目有两种情况：
1.小于等于k个，那我们直接全部取出即可
2.大于k个，那么我们就把r从小到达取出k个即可（即使没有取完也只取k个）

之所以当快递数大于k个时我们不把它全部取完是因为我们先把必须要取的取了，那么剩余的快递如果还没有到达截至时间，我们可以稍微等等，之后或许可以与其他后到的快递一起取出，这样答案或许会更优。

#include
#define LL long long
#define MIN 0xc0c0c0c0c0c0c0c0
#define PII pair
#define x first
#define y second
using namespace std;

const LL N = 4e5+100;
LL n,k;
PII a[N];
priority_queue< PII , vector , greater > q;

void solve()
{
	LL ans = 0;
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i].x,&a[i].y);
	}
	sort( a+1,a+n+1 );
	while( !q.empty() ) q.pop();
	q.push( { a[1].y,a[1].x } );
	LL t = a[1].y;
	for(int i=2;i<=n;)
	{
		while( i<=n && ( t==-1 || a[i].x<=t ) )
		{
			q.push( { a[i].y,a[i].x } );
			if( t==-1 ) t = a[i].y;
			else t = min( t,a[i].y );
			i++;
		}
		if( q.size()<=k ){
			ans++;
			while( !q.empty() ) q.pop();
			t = -1;
		}
		else if(q.size()>0){
			LL h = k;
			ans++;
			while( h-- ) q.pop();
			t = q.top().first;
		}
	}
	ans += ( ( q.size()+k-1 )/k );
	printf("%lldn",ans);
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while( t-- )
	solve();
	return 0;
}

题意：给定n个城市，q个询问,第k个城市有一个属性 w k w_k wk​，对于每一个询问q给定一个点 ( x , y ) (x,y) (x,y)，这个点到第k个城市 ( x i , y i ) (x_i,y_i) (xi​,yi​)的距离是 d i s t = m i n ( ∣ x − x k ∣ + ∣ y − y k ∣ , w k ) dist = min(lvert x-x_k rvert + lvert y-y_k rvert , w_k) dist=min(∣x−xk​∣+∣y−yk​∣,wk​)，问这个点到n个城市中 d i s t dist dist最大值是多少。

idea：式子中的 ∣ x − x k ∣ + ∣ y − y k ∣ lvert x-x_k rvert + lvert y-y_k rvert ∣x−xk​∣+∣y−yk​∣要同时考虑两维的限制，对于这个曼哈顿距离我们可以转成切比雪夫距离。关于切比雪夫距离推荐看这个大佬的博客。

1. 首先考虑没有 w k w_k wk​限制的情况，其实这就是经典的切比雪夫的套路，把点 ( x i , y i ) (x_i,y_i) (xi​,yi​)变成 ( x i + y i , x i − y i ) (x_i+y_i,x_i-y_i) (xi​+yi​,xi​−yi​)，这样转换后的点之间的切比雪夫距离就是原图中的哈夫曼距离。那么求答案就变成了求 m a x ( ∣ x ′ − x k ′ ∣ , ∣ y ′ − y k ′ ∣ ) max( lvert x^{'} - x_{k}^{'} rvert , lvert y^{'} - y^{'}_{k} rvert ) max(∣x′−xk′​∣,∣y′−yk′​∣)这其实就是在 x ′ − x k ′ , x k ′ − x ′ , y ′ − y k ′ , y k ′ − y ′ x^{'} - x_{k}^{'} , x_{k}^{'} - x^{'} , y^{'} - y^{'}_{k} , y^{'}_{k} - y^{'} x′−xk′​,xk′​−x′,y′−yk′​,yk′​−y′四个值之间取最max值。分别记录 x k ′ , − x k ′ , y k ′ , − y k ′ x_{k}^{'} , -x_{k}^{'} , y_{k}^{'} , -y_{k}^{'} xk′​,−xk′​,yk′​,−yk′​ 的最大值即可在 O(1) 时间内求出所有点到给定点切比雪夫距离的最大值。

2.现在考虑加入 w k w_k wk​ 的限制。将所有城镇按照 w k w_k wk​ 从小到大排序，并记录排序后每个后缀的 x k ′ , − x k ′ , y k ′ , − y k ′ x_{k}^{'} , -x_{k}^{'} , y_{k}^{'} , -y_{k}^{'} xk′​,−xk′​,yk′​,−yk′​ 的最大值，用于 O(1) 求给定点 到该后缀中所有点的距离最大值。选取按 w k w_k wk​ 排序后的第 k 个城镇，可以O(1) 求出给给定点到第 k…n 个城镇的距离最大值d，有两种情况：
（1） w k < d w_k < d wk​ 城镇的 w w w 值均不超过 w k w_k wk​，因此它们不可能接着更新答案，考虑范围缩小至 [ k + 1 , n ] [k + 1, n] [k+1,n]。
(2) w k ≥ d w_k ≥ d wk​≥d，那么第 k . . n k..n k..n 个城镇对答案的贡献为 d d d。用 d d d 更新答案后，考虑范围缩小至 [ 1 , k − 1 ] [1, k − 1] [1,k−1]。
容易发现每次考虑的范围都是一个区间，如果每次取 k 为区间的中点，那么二分迭代 O(log n)次即可得到最优解。

#include
#define LL long long
#define MIN 0xc0c0c0c0c0c0c0c0
using namespace std;

const LL N = 1e5+100;
LL n,m;

struct point
{
	LL x,y,w;
}e[101010];
bool cmp(point a,point b)
{
	return a.w
	LL p,q,k,xx,yy;
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld %lld",&p,&q,&k);
		e[i].x = p+q;
		e[i].y = p-q;
		e[i].w = k;		
	}
	sort( e+1,e+n+1,cmp );
	a[n+1] = b[n+1] = c[n+1] = d[n+1] = MIN;
	for(int i=n;i>=1;i--)
	{
		a[i] = max( a[i+1] , -e[i].x );
		b[i] = max( b[i+1] , e[i].x );
		c[i] = max( c[i+1] , -e[i].y );
		d[i] = max( d[i+1] , e[i].y );
	}
	while( m-- )
	{
		LL ans = 0,temp;
		scanf("%lld %lld",&p,&q);
		xx = p+q,yy = p-q;
		LL l = 1,r = n;
		while( l<=r )
		{
			LL mid = (l+r)>>1;
			temp = xx + a[mid];
			temp = max( temp , b[mid] - xx );
			temp = max( temp , yy+c[mid] );
			temp = max( temp , d[mid]-yy );
			if( temp>=e[mid].w )
			{
				l = mid+1;
				ans = max( ans,e[mid].w );
			}
			else 
			{
				r=  mid-1;
				ans = max( ans,temp );
			}
		}
		printf("%lldn",ans);
	}
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while( t-- )
	solve();
	return 0;
}