算法基础训练 50 题（二） 贪心

发表于 更新于 分类于 ，

#JC0201.# 活动安排

题目描述

对数据按照结束时间从小到大排序，相同结束时间的按开始时间从大道小排序。然后使用一个变量记录时间指针，不断选取开始时间大于等于时间指针的会议并把指针移到该会议的结束时间。

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
#include<bits/stdc++.h>
pair<int,int> p[1001];
int n,ans,t;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    F(i,1,n)
    {
        CI p[i].second>>p[i].first;
    } 
    sort(p+1,p+n+1);

    ans=1;
    t=p[1].first;
    F(i,2,n)
    {
        if (p[i].second>=t)
        {
            ans++;
            t=p[i].first;
        }
    }

    CO ans L;
    return 0;
}

#JC0202.# 种树

题目描述

对种树区间按照结束位置从小到大排序，对于相同结束位置的按照开始位置从大到小排序。然后用一个数组模拟种树的情况，对于每一种种树区间从区间末尾往前遍历：如果该地已有树，待种树减一；如果没有树，则种树，已种树加一，待种树减一，直到待种树为零。

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
#include<bits/stdc++.h>
int n,m,a[30004],ans;
struct tree{
    int s,e,n;
} t[10001];

bool cmp(tree t1,tree t2)
{
    if (t1.e<t2.e) return 1;
    if (t1.e==t2.e) return t1.s>t2.s;
    return 0;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    F(i,1,m)
    {
        CI t[i].s>>t[i].e>>t[i].n;
    }
    sort(t+1,t+m+1,cmp);
  
    F(i,1,m)
    {
        for (int j=t[i].s;j<=t[i].e&&t[i].n;j++)
            if (a[j]) t[i].n--; 

        for (int j=t[i].e;j>=t[i].s&&t[i].n;j--)
            if (!a[j])
            {
                t[i].n--;
                ans++;
                a[j]=1;
            }
    }
    CO ans L;
    return 0;
}

#JC0203.# 喷水装置

题目描述

首先要将这个二维问题转换为一维问题，在输入时过滤掉所有半径小于等于草坪宽度一半的值，然后再利用勾股定理算出每个喷头在草坪的长边上能覆盖的范围并记录起始终止值。对起始值从小到大排序。然后使用一个指针记录当前喷水覆盖到的位置。遍历所有的喷头，先找到能覆盖当前指针的所有喷头中能覆盖最远的那个喷头，打开这个喷头并将指针移到这个喷头的覆盖终止值处。

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
62
#include<bits/stdc++.h>
int t,n,l,w,ans;
double z;
struct p{
    int x,R;
    double l,r;
}a[20000];

bool cmp(p a1,p a2)
{
    return a1.l<a2.l;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n>>l>>w;
        F(i,1,n)
        {
            CI a[i].x>>a[i].R;
            if (a[i].R<=w/2)
            {
                i--;
                n--;
                continue;
            }
            a[i].l=max(0.0,a[i].x*1.0-sqrt(a[i].R*a[i].R*1.0-w*w/4.0));
            a[i].r=min(l*1.0,a[i].x*1.0+sqrt(a[i].R*a[i].R*1.0-w*w/4.0));
        }
        sort(a+1,a+n+1,cmp);
        int i=0;
        ans=0;
        z=0;
        double m;
        while (i<n)
        {
            i++;
            if (z>=l) break;
            m=a[i].r;
            while (i<n&&a[i+1].l<=z)
            {
                i++;
                m=max(m,a[i].r);
            }
            if (a[i].l<=z)
            {
                ans++;
                z=m;
            }
            else 
            {
                ans=-1;
                break;
            }
        }
        CO ans L;
    }
    return 0;
}

#JC0205.# 智力大冲浪

题目描述

对所有题目按照扣款从大到小排序。再用一个时间数组模拟做题情况。遍历每一道题，从截止时间从后往前找，直到找到空闲的时间并标记，如果没有空闲时间，就进行扣款。

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
#include<bits/stdc++.h>
int w,n;
int b[600];
struct s{
    int t,w;
} a[600];

bool cmp(s a1,s a2)
{
    return a1.w>a2.w;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI w>>n;
    F(i,1,n)
        CI a[i].t;
    F(i,1,n)
        CI a[i].w;
    sort(a+1,a+n+1,cmp);

    F(i,1,n)
    {
        int t=a[i].t;
        while (b[t]&&t>0)
            t--;
        if (t==0) w-=a[i].w;
        else
        {
            b[t]=1;
        }
    }
    CO w L;
    return 0;
}

#JC0206.# 纪念品分组

题目描述

先将奖品按价格从小到大排序，然后将价格大于上限的奖品数量记录下来，并用指针记录下第一个大于上限的奖品的前一个位置，然后再用一个指针指向第一个奖品，两两配对，如果价格之和小于上限就记为一组，两个指针同时移动；如果价格之和大于上限，指向末尾的指针单独向前移动，自己记为一组。

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
#include<bits/stdc++.h>
int w,n,a[30001];
int main()
{
    cin>>w>>n;
    for (int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int x=w-a[0],s=0,i,l,r;
    for (i=n-1;i>=0;i++)
        if (a[i]>w) s++;
        else break;

    l=0;
    r=i;
    while (l<=r)
    {
        if (a[l]+a[r]<=w) 
        {
            l++;
            r--;
        }
        else r--;
        s++;
     }
     cout<<s<<endl;
     return 0;
}

#JC0207.# 数列分段

题目描述

进行模拟即可。不断增加记录的和，直到超过最大值，然后重新开始记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
int n,m,ans=1,t,x;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    F(i,1,n)
    {
        CI x;
        if (x+t>m)
        {
            ans++;
            t=x;
        }
        else t+=x;
    }   
    CO ans L;
    return 0;
}

#JC0208.# 线段

题目描述

对线段按结束位置从小到大排序。用一个指针记录位置，遍历每一个线段，找出起止位置大于等于指针的线段并将指针指向结束位置。

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
#include<bits/stdc++.h>
int n,ans;
struct s{
    int s,e;
} a[1000006];

bool cmp(s a,s b)
{
    return a.e<b.e;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    F(i,1,n)
        CI a[i].s>>a[i].e;
    sort(a+1,a+n+1,cmp);

    int i=0;
    int t=0;
    while (i<n)
    {
        i++;
        while (a[i].s<t&&i<n)
            i++;
        if (a[i].s>=t) 
        {
            t=a[i].e;
            ans++;
        }
    }

    CO ans L;
    return 0;
}

#JC0209.# 家庭作业

题目描述

将作业按照学分从大到小排序。用一个时间数组记录做题情况。遍历每个作业，从截止时间从后往前遍历，直到找到空闲的时间并标记，累加学分。但是直接这样做会超时，所以还需要优化。再用另一个时间数组，被标记时表示从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
#include<bits/stdc++.h>
int n,ans,t[700005],e[700005];
struct s{
    int t,w;
} a[1000006];

bool cmp(s a,s b)
{
    return a.w>b.w;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    F(i,1,n)
        CI a[i].t>>a[i].w;
    sort(a+1,a+n+1,cmp);
  
    F(i,1,n)
    {
        if (e[a[i].t]) continue;
        int p=a[i].t;
        while (t[p]&&p>0&&e[p-1]!=1)
            p--;
        if (p>0&&!(t[p]&&e[p-1]))
        {
            t[p]=1;
            ans+=a[i].w;
        }
        else e[a[i].t]=1;
    }
    CO ans L;
    return 0;
}