POJ 1723 SOLDIERS

题目地址:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1723

纯数学题。
网上这题解答的太多了,copy一份过来:

解答 首先分开x和y坐标处理。首先看y坐标,对y坐标排序之后就可以轻松求出中位数,进而计算出移动步数。麻烦一点的是x坐标。首先我们对输入的点按照x坐标递增排序。排序后所有点的相对位置和最终要求的排列的相对位置是一致的。 如果排序后点p在q左边,而最终的排列q在p左边,那么可以通过交换两者的位置,一个步数增加,一个步数减少,总和是不变的。我们现在的任务是,找出一条“左边线”,让所有点从这条左边线开始依次排列。由于排序后的点相对位置和最终是一致的,我们按照排序后的下标0~n-1,在排序后点的横坐标基础上依次减去0、1、2……n-1,得到的点被横向移动后,应该聚集到那条“左边线”,而这个移动过程应该消耗最少的步数!对了!问题就转化为跟y坐标一样的处理方法了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>   
#include <algorithm>
using namespace std;
 
int main() {   
    int n, x[10000], y[10000];   
    scanf("%d", &n);   
    for (int i = 0; i < n; i++)   
        scanf("%d %d", &x[i], &y[i]);   
    sort(x, x + n);   
    sort(y, y + n);   
    for(int i = 0; i < n; i++)   
        x[i] -= i;   
    sort(x, x + n);   
    int ans = 0;   
    for (int i = 0; i < n/2; i++)   
        ans += x[n - 1 - i] - x[i] + y[n - 1 - i] - y[i];   
    printf("%d\n", ans);     
    return 0;   
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《POJ 1723 SOLDIERS》有384个想法

发表评论

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