士兵(0x05 排序)

简介: 笔记

士兵


题意

格格兰郡的 N 名士兵随机散落在全郡各地。


格格兰郡中的位置由一对 (x,y) 整数坐标表示。


士兵可以进行移动,每次移动,一名士兵可以向上,向下,向左或向右移动一个单位(因此,他的 x 或 y 坐标也将加 1 或减 1)。


现在希望通过移动士兵,使得所有士兵彼此相邻的处于同一条水平线内,即所有士兵的 y 坐标相同并且 x 坐标相邻。


请你计算满足要求的情况下,所有士兵的总移动次数最少是多少。


需注意,两个或多个士兵不能占据同一个位置。


思路

首先我们可以想到,士兵在 x 轴上的移动和在 y 轴上的移动是互不影响的


对于 y 坐标,将问题转化为 选择 y 轴上的一个点,将所有士兵的 y 坐标移到那个点上的最小步数,可以发现是一个经典的中位数问题,算则所有士兵 y 轴坐标的中位数即可。


对于 x 坐标,不能将其转换为将所有士兵的 x 坐标移动到 x 轴上的某个点,所以不能用中位数问题解决。


因为移动前后所有士兵在 x 轴上的相对位置不发生改变,可以假设第一个士兵 x 1移动后的位置为 a ,第二个士兵 x 2移动后的位置为a+1,以此类推第 n 个士兵移动后的位置为 a+n−1

51.png


代码

#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
const int N = 1e4 + 10;
int n;
struct Node {
  int x;
  int y;
  bool operator<(Node& x) {
    return this->x < x.x;
  }
}node[N];
bool cmp(Node a, Node b) {
  return a.y < b.y;
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> node[i].x >> node[i].y;
  }
  int res = 0;
  sort(node + 1, node + 1 + n, cmp);
  int y = node[(n + 1) / 2].y;
  for (int i = 1; i <= n; ++i) {
    res += abs(y - node[i].y);
  }
  sort(node + 1, node + 1 + n);
  for (int i = 1; i <= n; ++i) {
    node[i].x -= i - 1;
  }
  sort(node + 1, node + 1 + n);
  for (int i = 1; i <= n; ++i) {
    res += abs(node[(n + 1) / 2].x - node[i].x);
  }
  cout << res << endl;
}
signed main() {
  // int t; cin >> t;
  // while (t--)
    solve();
  return 0;
}
目录
相关文章
|
3月前
|
算法
AcWing 1360. 有序分数(每日一题)
AcWing 1360. 有序分数(每日一题)
869. 重新排序得到 2 的幂【我亦无他唯手熟尔】
869. 重新排序得到 2 的幂【我亦无他唯手熟尔】
52 0
|
8月前
【每日一题Day355】LC1402 做菜顺序 | 贪心+排序
【每日一题Day355】LC1402 做菜顺序 | 贪心+排序
56 0
|
算法 测试技术 C#
一题三解(暴力、二分查找算法、单指针):鸡蛋掉落
一题三解(暴力、二分查找算法、单指针):鸡蛋掉落
|
容器
剑指offer 69. 扑克牌的顺子
剑指offer 69. 扑克牌的顺子
101 0
[leetcode 324] 摆动排序 II 思维+排序
[leetcode 324] 摆动排序 II 思维+排序
87 0
|
设计模式 Java 编译器
这5个集合方面的问题,你都能答对吗?
这5个集合方面的问题,你都能答对吗?
这5个集合方面的问题,你都能答对吗?
|
人工智能
LeetCode 950. 按递增顺序显示卡牌
牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。
109 0
剑指 Offer 61. 扑克牌中的顺子(简单,哈希表)
剑指 Offer 61. 扑克牌中的顺子(简单,哈希表)
78 0
剑指 Offer 61. 扑克牌中的顺子(简单,哈希表)

热门文章

最新文章

下一篇
开通oss服务