网易2018年校招真题----堆棋子

题目描述        

小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.

输入描述:

输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数
第二行为n个棋子的横坐标x[i](1 ≤ x[i] ≤ 10^9)
第三行为n个棋子的纵坐标y[i](1 ≤ y[i] ≤ 10^9)

输出描述:

输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格

如样例所示:
对于1个棋子: 不需要操作
对于2个棋子: 将前两个棋子放在(1, 1)中
对于3个棋子: 将前三个棋子放在(2, 1)中
对于4个棋子: 将所有棋子都放在(3, 1)中

示例1

输入

复制

4
1 2 4 9
1 1 1 1

输出

复制

0 1 3 10

解题思路

 刚开始wa了3发，数据只过了50%，还好有错误数据提醒，发现了一组神奇的数据（4     15 15 14 16   14 16 15 15），之前的思路是暴力出一个点存在最小距离，枚举的是所有给出的点，然后根据这个数据发现有些数据不一定是给出的点，但是可以肯定的是那个点的横坐标和纵坐标是在给出的X数组和Y数组中的，然后只要枚举给出所有点的横坐标和纵坐标就可以了

AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define INF 1e9
using namespace std;
long long int x[55],y[55],n,vis[55],dis[55];
int main()
{
    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
            cin>>x[i];
        for(int i=1; i<=n; i++)
            cin>>y[i];
        cout<<0<<" ";
        for(int i=1; i<=n; i++)
            dis[i]=INF;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                int num=0;
                for(int k=1; k<=n; k++)
                {
                    vis[num++]=abs(x[i]-x[k])+abs(y[j]-y[k]);
                }
                sort(vis,vis+n);
                long long int flag=0;
                for(int k=0; k<n; k++)
                {
                    flag+=vis[k];
                    dis[k]=min(dis[k],flag);
                }
            }
        }
        for(int i=1; i<n; i++)
        {
            if(i<n-1)
                cout<<dis[i]<<" ";
            else
                cout<<dis[i]<<endl;
        }
    }
    return 0;
}