官方题解

T3 午枫的分割数组

题目大意

小午可以将一个数组分成前后两部分，第一部分给小午，第二部分给小枫，之后小午和小枫分别可以在各自的数组中选取 $k_1$ 和 $k_2$ 个数，然后比较两人选出的数的众数，大的一方获胜。判断小午是否可以获胜。

解题思路

题目中所选的数中数量最多的数称为众数，以下都称众数。

考虑当前有一个数组，最多选 $k$ 个数，如何让选出来的数的众数最大，显然，我们只要选一个最大的数即可。

那么对于小午来说，他需要让小枫拿到的数尽可能少，因为小枫拿到越少的数，能选出比小午大的数的可能就更小。所以小午的最优选择一定是把前 $n-1$ 个数分给自己，最后一个数分给小枫。

时间复杂度 $O(n)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n,k1,k2;cin>>n>>k1>>k2;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    int mx=*max_element(a.begin()+1,a.begin()+n);
    if(mx>a[n]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}