题解 - 南师大算法竞赛域 - Vijos

2

njnu19210134 (Rakan) LV 9 @ 3 年前

小蒟蒻第一次写题解，大佬们多指正。
这题的思路可以从摘得高的苹果开始，选定这个苹果，再再一堆陶陶里从上向下查找，能摘到就抵消掉，最后统计剩下的陶陶。
为了方便从高向低，这里我们借鉴桶排序的思路，建立一个二维数组，第一个参数代表高度，第二个参数0代表苹果，1代表陶陶，再输入数据。

#include<bits/stdc++.h>
using namespace std;
int t[301][2];
int main()
{
    int m,n;
    cin>>n>>m;
    int num;
    for(int i=0;i<n;i++){
        cin>>num;
        t[num][0]++;
    }
    for(int i=0;i<m;i++){
        cin>>num;
        t[num][1]++;
    }
    
    
    return 0;
}

将建立数组的代码放在main外面来自动初始化成全0。
然后利用for循环，将i作为苹果的高度参数，j作为陶陶的高度参数，初始化后进行判断和抵消。
先初始化j为1避免直接break，i初始化为最高的高度三百，再把i-1赋值给j再往下，毕竟苹果此时最高也只能摘到比他第一格的陶陶（我直接就是以为相等也能摘到然后8个wa），此时，如果i>j且i高度的苹果与j高度的陶陶都存在，那么抵消。如果j高度的陶陶不存在，j--查找低一格的陶陶，i高度的苹果不存在，跳出内循环进入外循环执行i--。

    int j=1;
    for(int i=300;i;){
        if(j==0) break;
        j=i-1;
        if(t[i][0]==0){
            i--;
            continue;
        }
        while(j){
            if(i>j&&t[i][0]>0&&t[j][1]>0){
                t[i][0]--;
                t[j][1]--;
            }
            if(t[j][1]==0) j--;
            if(t[i][0]==0) break;
        }
    }

注意边界条件比如高度为0的陶陶不能摘之后就可以统计sum并输出了。总程序如下：


#include<bits/stdc++.h>
using namespace std;
int t[301][2];
int main()
{
    int m,n;
    cin>>n>>m;
    int num;
    for(int i=0;i<n;i++){
        cin>>num;
        t[num][0]++;
    }
    for(int i=0;i<m;i++){
        cin>>num;
        t[num][1]++;
    }
    int j=1;
    for(int i=300;i;){
        if(j==0) break;
        j=i-1;
        if(t[i][0]==0){
            i--;
            continue;
        }
        while(j){
            if(i>j&&t[i][0]>0&&t[j][1]>0){
                t[i][0]--;
                t[j][1]--;
            }
            if(t[j][1]==0) j--;
            if(t[i][0]==0) break;
        }
    }
    int sum=0;
    for(j=0;j<=300;j++)
    {
        sum+=t[j][1];
    }
    cout<<sum;
    return 0;
}

吴鹏飞 @ 2 年前

谢谢，有一点我怎么也想不通，你解出来了，很厉害。

0
无影 (吴鹏飞) LV 10 @ 2 年前

确定不是陶陶摘苹果？

ID: 1125
难度: 9
分类: 贪心点击显示
标签: (无)
递交数: 1434
已通过: 98
通过率: 7%
上传者: yejun