[cf] 766 div2 B. Not Sitting

前言

t a g : tag : tag: 奇奇怪怪的题意 *1300 贪心 思维 传送门 :

题意 : 给定一个 N × M N×M N×M的网格, A A A可以将 k k k个网格涂成红色, B B B首选选择一个网格, B B B不喜欢红色网格,然后 A A A再选择一个网格,最后询问对于 k ∈ [ 0 , n ∗ m − 1 ] k\in[0,n*m-1] k∈[0,n∗m−1], B B B想离 A A A近点, A A A想离 B B B远点的最优距离 ∣ x A − x B ∣ + ∣ y a − y b ∣ |x_A-x_B|+|y_a-y_b| ∣xA​−xB​∣+∣ya​−yb​∣

思路 : 个人感觉题意过于诡异

首先正常思考, B B B每次选择坐中间必然是最优的,然后 A A A为了原离 B B B必然会选择角落

这是在不考虑涂色的情况下,但是如果涂色了怎么办呢?

对于每个 i , j i,j i,j我们都对其进行估算最优选择,然后将其放入容器里面

对容器进行排序,那么从小到大拿就是 k ∈ [ 0 , n ∗ m − 1 ] k\in[0,n*m-1] k∈[0,n∗m−1]的答案

看了很多博客的证明,还是没想通,幸好有样例不然做不出来了QAQ

code :

void solve(){
	int n,m;cin>>n>>m;
	
	int d  = (n -  (n+1)/2)  + (m - (m+1)/2);
	
	vector v;
	
	
	for(int i=1;i