P11231题解（题解里的太难了只能在写一篇）

· · 个人记录

O(n)做法。

题意简述：

给你n个数，每个数r[i]攻击力和防御力都是它本身，每个数r[i]只能进攻一次，如果你进攻的数的r[i]\le自己的数,则那个数退出游戏。

现在要求一组攻击数据,使得最后剩下的数尽可能的少。

题目分析：

数据：
5
1 2 3 1 2

容易发现，只要用两个2分别打两个1，再用3打一个2，就能得到题目的输出。

那么规律是什么呢？
在这组数据里看不出来，再附上我的数据： 

7
1 3 2 4 3 3 3

再推一下：2打1，一个3打2，一个4打3。 输出就是4。

发现规律了吗？没错，输出结果就是输入的数中重复最多的数。

题目做法

用一个桶t[100005]来存，每次输入时更新桶，同时更新最大值。

\color{green}{AC记录}

here

Code:

#include<bits/stdc++.h>
using namespace std;
int n;
int t[100005],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int r;
        cin>>r;
        t[r]++;
        ans=max(ans,t[r]);
    }
    cout<<ans;
    return 0;
}