【每日一题1】AcWing 104. 货仓选址

发表于 更新于 分类于 Valine：
本文字数： 465 阅读时长 ≈ 1 分钟

Day1 AcWing 104. 货仓选址

思路

中位数是最优解

相关题目

拓展知识

  • 将第n个数放在正确的位置上nth_element
  • nth_element(nums.begin(),nums.begin()+k,nums.end(),greater<int>()); 第k大的数
  • 位运算 i>>1
  • for() shift 9 0，快速退出括号

nth_element拓展

  1. 2021/2/3 lc 480.滑动窗口中位数
  2. 直接将求完的nth_element保存，不要连续求两次
  3. 若需要将两个数据放在正确的位置，先对后面的数求nth_element，再求前面的
    nth_element(nums.begin(),nums.begin()+n+1,nums.end());
    nth_element(nums.begin(),nums.begin()+n,nums.end());
  4. 先排前面再排后面，会导致前面已经排好序的位置被打乱。
1
2
3
4
5
6
7
8
9
10

1 4 7 1 3 8 4 5 //初始
3 1 1 4 4 5 7 8 //先排n
4 1 1 3 4 5 7 8 //再排n+1

1 1 3 4 4 5 7 8 //正确排序

1 4 7 1 3 8 4 5 //初始
3 1 1 4 4 5 7 8 //先排n+1
3 1 1 4 4 5 7 8 //再排n

写法1 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);
    cout << res << endl;
    return 0;
}

写法2 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[i / 2]);
    cout << res << endl;
    return 0;
}

写法3 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    nth_element(a, a + n / 2, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);
    cout << res << endl;
    return 0;
}