题目链接

题目大意

给定n个点,找到若干个中心,使得中心到各个点的曼哈顿距离之和最小。输出中心个数

解题思路

首先,假设中心横坐标首先选在x_1(假设已经从小到大排序过),那么X方向上的曼哈顿距离之和sum = \sum_{i = 2}^{n}(x_i-x_1)

假设我们横坐标移动到x_2,那么此时 sum相对于上一步,相当于减去\sum_{i = 3}^{n}(x_2-x_1),加上\sum_{i = 1}^{1}(x_2-x_1)

假设我们横坐标移动到x_3,那么此时 sum相对于上一步,相当于减去\sum_{i = 4}^{n}(x_3-x_2),加上\sum_{i = 1}^{2}(x_3-x_2)

… …

假设我们横坐标移动到x_p,那么此时 sum相对于上一步,相当于减去\sum_{i = p+1}^{n}(x_p-x_{p-1}),加上\sum_{i = 1}^{p-1}(x_p-x_{p-1})


不难发现,n较大时sum起初下降,因为减少量多于增加量;与之对应,sum最终会上升,因为反方向而言,增加量多于减少量。因此,sum是一个单峰函数,先下降,再上升。

不妨将下标取中位数,mid

假如p=mid,若挪至p=mid+1,则减去\sum_{i = mid+2}^{n}(x_{mid+1}-x_{mid}),加上\sum_{i = 1}^{mid}(x_{mid+1}-x_{mid}) 显然,此时增加量更多,sum将会增大

若挪至p=mid-1,亦然,增加量更多,sum增大。

综上所述,当取中位数时,总曼哈顿距离最小,同理适用于Y方向。


还有一点小问题:

若n为奇数,则X方向Y方向的中位数x_{mid}y_{mid}所在位置即为中心。显然,中心有且仅有一个。

若n为偶数,中心选取在x_{\lfloor mid \rfloor}x_{\lceil mid \rceil}之间且y不变(定义double mid=(l+r)/2)时,sum值不变。同理,在y_{\lfloor mid \rfloor}y_{\lceil mid \rceil}之间且x不变时,sum值不变

因此,在x_{\lfloor mid \rfloor} x_{\lceil mid \rceil}y_{\lfloor mid \rfloor} y_{\lceil mid \rceil}之间的区域,均可以为中心。

由于c++实际上进行整数除法时,舍去小数位(mid即向下取整)。因此,向上取整可写为mid+1【详见代码】

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+7;
int T;
int n,m;
int a[N];
int b[N];

signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
        }
        if(n%2 == 1){
            cout<<1<<endl;
            continue;
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        int mid=n/2;
        cout<<(a[mid+1]-a[mid]+1)*(b[mid+1]-b[mid]+1)<<endl;
    }
    return 0;
}
分类: 补题

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注