2 条题解

  • 2
    @ 2021-08-24 01:13:28

    小蒟蒻第一次写题解,大佬们多指正。
    这题的思路可以从摘得高的苹果开始,选定这个苹果,再再一堆陶陶里从上向下查找,能摘到就抵消掉,最后统计剩下的陶陶。
    为了方便从高向低,这里我们借鉴桶排序的思路,建立一个二维数组,第一个参数代表高度,第二个参数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;
    }
    
    
    • @ 2022-07-31 15:31:32

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

  • 0
    @ 2022-07-31 15:32:27

    确定不是陶陶摘苹果?

  • 1

信息

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