算法Basic--贪心

Posted on Edited on In Views:

区间问题

在当前选择局部最优解，依次这样选择能够到达全局最优解。

区间选点

  • 1、将每个区间按右端点从小到大排序；
  • 2、从前往后依次枚举每个区间，如果当前区间已经包含点，则pass；否则选择当前区间的右端点。

证明：按照上述规则选出来的所有点数记为cnt，题目要求为ans，则ans<=cnt，cnt同时代表了我们目前有cnt个区间，因此ans最少需要cnt个点，因此ans>=cnt，因此上述cnt便是解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 +10;
struct Block{
    int l, r;
    
    bool operator < (const Block &W) const
    {
        return r < W.r;
    }
}bk[N];
int main()
{
    int n; 
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        bk[i] = {a, b};
    }
    
    sort(bk, bk + n);
    
    int res = 1, maxr = bk[0].r;
    for(int i = 1; i < n; i ++)
    {
        if(bk[i].l > maxr)
        {
            res++;
            maxr = bk[i].r;
        }
    }
    
    cout << res <<endl;
    
    return 0;
}

最大不相交区间数量

按照区间的右端点排序，因为我们要选择不相交区间，那么右端点最小的区间是最贪心的选择，这下选择合并其他区间时，其他区间的左边可以更靠左，也就是选择范围更广。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

struct Block{
    int l, r;
    bool operator < (const Block &W) const
    {
        return r < W.r;
    }
}block[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        block[i] = {a, b};
    }
    
    sort(block, block + n);
    
    int res = 1;
    int maxr = block[0].r;
    for(int i = 1 ; i < n; i++)
    {
        if (block[i].l > maxr)
        {
            res++;
            maxr = block[i].r;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

区间分组

  • 1、将所有区间按左端点从小到大排序；
  • 2、从前往后处理每个区间，判断能否将其放到某个现有的组中；即 L(i) > Max_r，不能的话，意味着当前组与当前区间有交集，重新开一个组放入当前区间；能的话，将当前区间放入组内，更新Max_r。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
const int N = 1e5 +10;

int n;


struct Block{
    int l, r;
    bool operator < (const Block &W) const
    {
        return l < W.l;
    }
}bk[N];


int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        bk[i] = {a, b};
    }
    
    sort(bk, bk + n);
    
    priority_queue<int, vector<int>, greater<int>> q; //记录所有区间的右边界，并随时查看边界里最小的值
    
    for(int i = 0; i < n; i ++)
    {
        if(q.empty() || q.top() >= bk[i].l)
            q.push(bk[i].r);
        else //区间合并
        {
            q.pop();
            q.push(bk[i].r); 
        }
    }
    cout << q.size() << endl;
    
    return 0;
}

区间覆盖

1、将所有区间按照左端点从小到大排序；

2、从前往后依次枚举每个区间，在所有能覆盖目标区间start的区间中，选择右端点值最靠右（最大）的区间；然后将start更新成右端点的最大值；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

struct Block{
    int l, r;
    bool operator < (const Block &W) const
    {
        return l < W.l;
    }
}block[N];

int s, t, n;

int main()
{
    scanf("%d%d%d", &s, &t, &n);
    for(int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        block[i] = {a, b};
    }
    
    sort(block, block + n);
    
    int res = 0, r = -2e9;
    bool find = false;
    for(int i = 0; i < n; i ++)
    {
        int l = i;
        while(l < n && block[l].l <= s)
        {
            r = max(r, block[l].r);
            l++;
        }
        res++;
        i = l - 1;
        if(r <= s) //情况1：不能覆盖
        {
            break;
        }
        if(r >= t) //情况2.1:完全覆盖
        {
            find = true;
            break;
        }
        else  //情况2.2:部分覆盖
        {
            s = r;
        }
    }
    
    if(!find) printf("%d", -1);
    else printf("%d", res);
    
    return 0;
    
}

Huffman树

合并果子

在路径上，叶子节点存在多少个父祖节点，就需要计算多少次该叶子节点的值。

1、挑两个权值最小的节点，它们是深度最深且可以互为兄弟（不一定作为兄弟）的节点。

2、贪心式地合并，即n-1的最优解是否一定是n的最优解？f(n) = f(n-1) + a + b，所有最小值都存在a+b，因此可以去掉a+b再考虑f(n-1).

实现：利用优先队列，只要堆中数目大于1便进行合并；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n, k;
int main()
{
    priority_queue<int,vector<int>, greater<int>> q;

    cin >> n;
    
    for(int i=0; i < n; i ++) 
    {
        cin >> k;
        q.push(k);
    }
    
    int res = 0;
    while(q.size() > 1)
    {
        auto a = q.top(); q.pop();
        auto b = q.top(); q.pop();
        
        res += a + b;
        q.push(a + b);
    }
    
    cout << res << endl;
    return 0;
}

排序不等式

排队打水

等待的总时间为$t_1 \times(n-1) + t_2 \times (n-2)+….$ ； 即贪心的可知，按照从小到大的顺序排队，总时间最小。

证明：反证法，交换t(i)与t(i+1)

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

using namespace std;

const int N = 1e5 + 10;

int t[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> t[i];
    sort(t, t + n);
    long long res = 0;
    for(int i = 0; i < n; i ++)
    {
        res += t[i] * (n - i - 1);
    }
    
    cout << res << endl;
    
    return 0;
}

绝对值不等式

货仓选址

每个商店的地址记为$x_i$，货仓地址记为$x$，总的距离为：$f(x)=|x_1 - x| + |x_2 - x| +…|x_n + x|$，

分组的思想：第一个x1和最后一个xn视为一组，即$f(x) =|x_1 - x| + |x_n - x|$，此时，x应该取a与b之间。

因此所有数的个数为奇数，则取中位数；偶数的话则取中间两个数之间， $f(x)$的大小即$|xn - x_1| +|x{n-1} - x_2| + … $。

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

using namespace std;

const int N = 1e5 + 10;
int t[N];

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

推公式

耍杂技的牛

目的：最大的危险系数中最小的。

结论：按照 $ w_i + s_i $ 从小到大的顺序排，最大的危险系数一定是最小的。

证明：贪心得到的答案 >= 最优解(min)； 需要证明贪心得到的答案<=最优解；

反证：

可知当交换第i和i+1位置的牛后，i+1位置上的牛的风险大于i位置的牛，并且风险增大了，因此违反了目的，结论成立。

第i个位置上的牛 第i+1个位置上的牛
交换前 $w1 + w_2 +..+w{i-1} - si= - s_i=> s{i+1}$ $w1 + w_2 +..+w{i} - s{i+1} =w{i} - s_{i+1}=>w_i + s_i $
交换后 $w1 + w_2 +..+w{i-1} - s{i+1} = - s{i+1}=>s_{i} $ $w1 + w_2 +..+w{i-1} +w{i+ 1} - s_i = w{i+ 1} - si =>w{i+ 1} + s_{i+1} $ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

typedef pair<int, int> PII;
const int N = 1e5 + 10;
PII t[N];

int main()
{
    int n; 
    cin >> n;
    
    for(int i = 0; i < n; i ++)
    {
        int w, s;
        cin >> w>> s;
        t[i] = {w + s, w};
    }
    
    sort(t, t + n);
    
    ll res = -2e9, sum = 0;
    for(int i = 0; i < n; i ++)
    {
        int w = t[i].second, s = t[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    
    cout << res << endl;
    
    return 0;
    
}