贪心算法专训题解

发表于 更新于 分类于 ，

P1007. 独木桥

题目描述

当两人面对面相碰时，两人都会转向行走， 那可以看成两个人交错而过。

求最小时间，计算出每个人到达两边的最小时间，所有时间中最大的一个即为所有人离开桥需要用的时间。

求最大时间，计算出每个人到达两边的最大时间，所有时间中最大的一个即为所有人离开桥需要用的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int main()
{
 	int l,n,a[5003];
    cin>>l>>n;
    for (int i=1;i<=n;i++)
    	cin>>a[i];
    // sort(a+1,a+n+1);
    int x=int(l/2.0+0.5);
    int ans1=0,ans2=0;
	for (int i=1;i<=n;i++)
        ans1=max(min(a[i],l+1-a[i]),ans1);
  
    for (int i=1;i<=n;i++)
        ans2=max(max(a[i],l+1-a[i]),ans2);

    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

P1031. [NOIP2002 提高组] 均分纸牌

题目描述

统计纸牌总数，计算平均数，即为每个纸牌堆的最终纸牌数。

从左往右遍历，如果当前纸牌堆不等于平均数，则将其与平均数的差累加的右侧的纸牌队：如果当前纸牌数大于平均数，则相当于把多出来纸牌放置到右侧；如果当前纸牌数小于平均数，则相等于从右侧索取纸牌。操作完成后增加一个操作计数。单次操作后当前纸牌堆的数量将会变成平均数，结束后所有的纸牌都将变成平均数。

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>
using namespace std;
int main()
{
    int a[10001];
    long long avg=0;
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        avg+=a[i];
    }
    avg/=n;

    int ans=0,x=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]!=avg)
        {
            a[i+1]=a[i+1]+a[i]-avg;
            ans++;
        }
    }
	cout<<ans<<endl;
    return 0;
}

P2695. 骑士的工作

题目描述

将头的大小和\(z_i\)都进行从小到大的排序，判断当前的\(z_i\)是否大于当前的头，大于的话计入金币，两个数组指针同时向后移动。否者\(z\)指针向后移动。

程序中使用小根堆实现排序。

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

int n,m;
int x;

priority_queue<int,vector<int>,greater<int> > q1;
priority_queue<int,vector<int>,greater<int> > q2;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    F(i,1,n)
    {
        CI x;
        q1.push(x);
    }
    F(i,1,m)
    {
        CI x;
        q2.push(x);
    }

    LL ans=0;
    while (!q1.empty() && !q2.empty())
    {
        if (q1.top()<=q2.top())
        {
            q1.pop();
            ans+=q2.top();
            q2.pop();
        }
        else
        {
            q2.pop();
        }
    }
    if (!q1.empty())
    {
        CO "you died!" L;
        return 0;
    }
    else CO ans L;
    return 0;
}

P5639. 【CSGRound2】守序者的尊严

题目描述

将连续的0或连续的1看成一块，数一共有多少块即可。

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

P1056. [NOIP2008 普及组] 排座椅

题目描述

先统计每一行和每一列一共有多少人会交头接耳，然后按数量从大到小排序，再从大到小记录前K、L个行列，最后按序输出即可。

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
int M,N,K,L,D;
int x,y,p,q;
map<int,int> k;
map<int,int> l;
pair<int,int> kk[1005];
pair<int,int> ll[1005];
int kkk[1005],lll[1005];

bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.second>b.second;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI M>>N>>K>>L>>D;
    F(i,1,D)
    {
        CI x>>y>>p>>q;
        if (x==p) l[min(y,q)]++;
        elif (y==q) k[min(x,p)]++;
    }

    int indexl = 1;
    for (auto i : l)
        ll[indexl++]=i;
    indexl--;

    int indexk=1;
    for (auto i:k)
        kk[indexk++]=i;
    indexk--;

    sort(kk+1,kk+indexk+1,cmp);
    sort(ll+1,ll+indexl+1,cmp);

    F(i,1,K)
        kkk[kk[i].first] = 1;
    F(i,1,L)
        lll[ll[i].first] = 1;

    F(i,1,M)
        if (kkk[i]) CO i P;
    cout<<endl;
    F(i,1,N)
        if (lll[i]) CO i P;
    cout<<endl;
    return 0;
}

P1090. [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

题目描述

因为每次合并果子时都会导致最先合并的果子被重复计算一次，所以让最少的果子堆重复记录最多次，最多的果子堆记录最少次，即每次合并数量最少的两堆果子，然后将合并后的果子堆放回队列。

使用小根堆可以实现每次取出最小的两堆果子，插入新的果子堆可以自动排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n,x,ans;
priority_queue<int,vector<int>,greater<int> > q;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    F(i,1,n) 
    {
        CI x;
        q.push(x);
    }
    F(i,1,n-1)
    {
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        ans+=a+b;
        q.push(a+b);
    }
    CO ans L;
  
    return 0;
}

P1106. 删数问题

题目描述

进行n次查找，每次查找都从头到尾遍历字符串然后找到第一个峰顶，删除后再消除前缀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
int n;
int a[1000];
string s;
int k;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI s;
    CI n;
    F(i,1,n)
    {
        int j=0;
        while (s[j]>=s[j-1]&&j<s.size())
            j++;
        s.erase(j-1,1);
        while (s[0]=='0')
            s.erase(0,1);
    }
    if (s.size()==0)
        CO 0 L;
    else
        CO s L;
    return 0;
}

P2630. 图像变换

题目描述

手推可得，图像的变化只会有8种，A、B、C、D、AA、AB、AC、AD。所以只需要判断属于这8种的哪一个就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a,b,c,d,e,f,g,h,i;
int A,B,C,D,E,F,G,H,I;
int main()
{
    CI a>>b>>c>>d>>e>>f>>g>>h>>i;
    CI A>>B>>C>>D>>E>>F>>G>>H>>I;
    if (A==g&&B==d&&C==a&&D==h&&E==e&&F==b&&G==i&&H==f&&I==c) CO "A" L;
    elif (A==c&&B==f&&C==i&&D==b&&E==e&&F==h&&G==a&&H==d&&I==g) CO "B" L;
    elif (A==c&&B==b&&C==a&&D==f&&E==e&&F==d&&G==i&&H==h&&I==g) CO "C" L;
    elif (A==g&&B==h&&C==i&&D==d&&E==e&&F==f&&G==a&&H==b&&I==c) CO "D" L;
    elif (A==i&&B==h&&C==g&&D==f&&E==e&&F==d&&G==c&&H==b&&I==a) CO "AA" L;
    elif (A==a&&B==b&&C==c&&D==d&&E==e&&F==f&&G==g&&H==h&&I==i) CO "AB" L;
    elif (A==a&&B==d&&C==g&&D==b&&E==e&&F==h&&G==c&&H==f&&I==i) CO "AC" L;
    elif (A==i&&B==f&&C==c&&D==h&&E==e&&F==b&&G==g&&H==d&&I==a) CO "AD" L;
    else CO "Poland cannot into space!!!" L;
    return 0;
}

P5514. [MtOI2019] 永夜的报应

题目描述

a^b<=a+b，所以要让异或和最小，那就让所有数字异或在一起就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
int n,ans,a;
int main()
{
    CI n;
    while (n--)
    {
        CI a;
        ans^=a;
    }
    CO ans L;
    return 0;
}