POJ 3269 中位数

刺骨的言语ヽ痛彻心扉 2021-12-22 14:17 246阅读 0赞

题意：  
![这里写图片描述][20160828134444298]  
![这里写图片描述][20160828134452424]

思路：  
这道题坑也不少。。 你准备好脑洞了么？

首先  
要认真审题 题目中有说：“没有两头牛的吃草位置是相邻的”  
这句话让我们省了很多的事儿 （Discuss里有的大神就入了这个坑了）

然后呢  
自然想到了中位数 （不要问我怎么想到的）

但是如果n为偶数怎么办呢 就取两个中间位置的数那段区间呗~

本以为随便搞搞

<table> 
 <thead> 
  <tr> 
   <th align="left">n的取值</th> 
   <th align="left">干啥</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">n为奇数</td> 
   <td align="left">找到中间点</td> 
  </tr> 
  <tr> 
   <td align="left">n为偶数</td> 
   <td align="left">找到矩形区间</td> 
  </tr> 
 </tbody> 
</table>

就像酱紫，就完了呢….

然而 我想简单了….

还有几步没有想到  
1. 中间的那个点被牛占了怎么办  
2. 矩形区间里面有牛怎么办

对于第一个问题  
遍历它旁边的所有点（上下左右） 找到合适的点（可能是好几个）并统计  
再重复一遍这句话“没有两头牛的吃草位置是相邻的”

对于第二个问题 判个重就OK了……

最后放一个毕克大爷的数据

![这里写图片描述][20160828140056100]

（我跟他的结果一样 嘿嘿）  
（不一样不就惨了嘛……）

//By SiriusRen 
    #include <cmath>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int n,xx[]={
         1,-1,0,0},yy[]={
         0,0,1,-1};
    struct Point{
         int x,y;}point[10005];
    bool cmp1(Point a,Point b){
         return a.x<b.x;}
    bool cmp2(Point a,Point b){
         return a.y<b.y;}
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&point[i].x,&point[i].y);
        if(n&1){
            int ans=0,l,r;
            sort(point+1,point+1+n,cmp1);
            int ansx=point[n/2+1].x;
            sort(point+1,point+1+n,cmp2);
            int ansy=point[n/2+1].y;
            for(l=n/2+1;l>=1;l--)
                if(point[l].y!=point[l-1].y)break;
            for(r=n/2+1;r<=n;r++)
                if(point[r].y!=point[r+1].y)break;
            for(int i=l;i<=r;i++){
                if(i==r) {
                    for(int i=1;i<=n;i++){
                        ans+=fabs(point[i].x-ansx);
                        ans+=fabs(point[i].y-ansy);
                    }
                    printf("%d 1\n",ans);
                    return 0;
                }
                if(ansx==point[i].x)goto end;
            }
            end:int answer=0x3ffffff,temp;
            for(int i=0;i<=3;i++){
                ans=0;
                int tempx=ansx+xx[i];
                int tempy=ansy+yy[i];
                for(int i=1;i<=n;i++){
                    ans+=fabs(point[i].x-tempx);
                    ans+=fabs(point[i].y-tempy);
                }
                if(answer>ans)answer=ans,temp=1;
                else if(answer==ans)temp++;
            }
            printf("%d %d\n",answer,temp);
        }
        else{
            sort(point+1,point+1+n,cmp1);
            int ansx=point[n/2].x,ans=0,ansx2=point[n/2+1].x,recs=0;
            sort(point+1,point+1+n,cmp2);
            int ansy=point[n/2].y,ansy2=point[n/2+1].y;
            for(int i=1;i<=n;i++)
                ans+=fabs(point[i].x-ansx),ans+=fabs(point[i].y-ansy);
            for(int i=1;i<=n;i++)
                if(point[i].x>=ansx&&point[i].x<=ansx2&&point[i].y>=ansy&&point[i].y<=ansy2)
                    recs++;
            printf("%d %d\n",ans,(ansx2-ansx+1)*(ansy2-ansy+1)-recs);
        }
    }

![这里写图片描述][20160828135914773]

转载于:https://www.cnblogs.com/SiriusRen/p/6532327.html

[20160828134444298]: /images/20211220/5841269396ad4e2ea63982043e653acf.png
[20160828134452424]: /images/20211220/1e9a6efa60a64e06ad620a6eee59ec4b.png
[20160828140056100]: /images/20211220/0f9eaf800abb4efb9e61ad9ba6fcbae5.png
[20160828135914773]: /images/20211220/1ac76cf3dadf4240bb5e05590f500e46.png