题目难度:一星
考察点:模拟、计数
方法:模拟、计数
- 分析:
由于整个屏幕有n列,那么如果想要得分的话就要从第1列到第n列都要有值才能得分,那么我们只需要对每个方块落在第几列进行计数,然后从第1列一直循环到第n列,判断哪列的计数值最小,最小值就是答案,输出即可。
举个例子:
3 6
1 2 3 1 1 2
上例表示一共有三列,6个1*1的方块,那么我们统计一下每一列的方块数:
第一列:有3个(数字1有三个)
第二列:有2个(数字2有二个)
第三列:有1个(数字3有一个)
所以以每列的个数最小值为最终答案,即小易能够得1分。
算法实现:
(0). 输入x,用一个数组用来计数a[x]++
(1). 从第1列遍历到第n列,找到计数数组的最小值
(2). 输出最终最小值结果
复杂度分析:
时间复杂度:O(n)
空间复杂度:O(n)代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1e3+5; int a[MAXN]; int main() { int n, m; cin>>n>>m ; for(int i=0; i<m; i++) { int x; cin>>x; a[x]++; } int ans = m; for(int i=1; i<=n; i++) ans = min(ans, a[i]); cout<<ans<<endl; return 0; }