【日常学习】【数学】codevs3625 士兵站队问题题解

深碍√TFBOYSˉ_ 2022-08-09 14:49 263阅读 0赞

题目描述 Description

在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点用整数坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一行。编程计算使所有士兵排成一行需要的最少移动步数。

输入描述 Input Description

第1行是士兵数n，1≤n≤10000。接下来n行是士兵的初始位置，每行有2个整数x和y，-10000≤x，y≤10000。

输出描述 Output Description

一个数据，即士兵排成一行需要的最少移动步数。

样例输入 Sample Input

1 2

2 2

1 3

3 -2

3 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

\-10000≤x，y≤10000

这道题···真是虚了···

先考虑纵坐标，要统一到一条线上。我们不妨想，对于最上方和最下的两个点，如果想让他们到某个点的垂直距离和最小，这个点一定在两点中间；对于任意一对点同理。因此对于最里面的一对点，也是这样。所以我们应该取这些点的中位数作为横坐标。

这就相当于：对于数轴上的一些点，选择一个点到所有点距离和最小，那么这个点是坐标为所有点中位数的那个点。

接下来，对于横坐标，如何确定X轴方向上的最佳的“最终位置”？  
共n个士兵  
他们相应的X轴坐标为：X0，X1，X2 …… …… Xn-1  
设，士兵需要移动到的“最终位置”的X轴坐标值为：k，k+1，k+2 …… …… k+（n-1）  
则所求最优步数S=|X0-k|+|X1- （k+1） |+|X2-（k+2）|+ …… +|Xn-1-（k+（n-1））|  
经过变形S=|X0-k|+|（X1-1）-k|+|（X2-2）-k|+ …… …… +|（Xn-1-（n-1））-k|  
注意到公式的形式与Y轴方向上的考虑一样，同样是n个已知数分别减去一个待定数后取绝对值，然后求和  
因此还是采用取中位数的办法求得k值，最后算出最优解。

这题我实在不想再说了，直接贴代码

然后我要去练基本算法了···

//soldiers
    //input output txt
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=10000+10;
    
    struct node
    {
        int x,y;
    }e[maxn];
    
    int n;
    long long ans=0;
    
    int cmpy(node a,node b)
    {
        return a.y
          
           >1;
        int midx=e[i].x;
        int l=midx,r=midx+1;
        int j=i+1;
        while (i>0)
        {
            ans+=abs(e[i].x-l);
            l--;
            i--;
        }
        while (j<=n)
        {
            ans+=abs(e[j].x-r);
            ++r;
            ++j;
        }
    */

今天实在是虚了。突如其来，如潮水一般的感情就这么涌过来把我扑倒在沙岸上，一时间心里百般滋味。

——不才明主弃，多病故人疏