2 条题解
-
2njnu19210134 (Rakan) LV 9 @ 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; }
-
02022-07-31 15:32:27@
确定不是陶陶摘苹果?
- 1