c++ T320258 划分众数

Question

划分众数

题目描述

给定一个序列 $a_1,a_2,\dots,a_n$ 。

如果一个长度为 $m$ 的序列中存在某个数字出现了严格大于 $\lfloor\frac{m}{2}\rfloor$ （ $m$ 除以 $2$ 后下取整）次，那么就称这个数字是该序列的严格众数。否则该序列没有严格众数。

请问是否存在一种方案，将 $a$ 划分为若干个区间（可以为 $1$ 个），使得这些区间互不相交且并集为整个序列，且每个区间形成的序列都没有严格众数？

一个测试点可能包含多组数据。

输入格式

第一行一个整数 $T$ ，表示测试组数。

接下来对于 $T$ 组数据中的每一组，输入两行（一个整数和一个序列），分别表示序列长度 $n$ 和序列 $a$ 。

输出格式

$T$ 行，每行一个字符串 Yes 或 No （不可改变大小写），表示该组数据是否有解。

样例 #1

样例输入 #1

2
6
1 1 4 5 1 4
4
2 3 3 3

样例输出 #1

Yes
No

提示

样例解释

对于第一组数据，下面给出一组构造方法：

将序列分为两段 1 1 4 5 和1 4`，由于两段都没有严格众数，所以满足题意。

对于第二组数据，可以证明无解。

数据范围

对于 $30%$ 的数据，满足 $n\leq 5$ 。

对于 $70%$ 的数据，满足 $n\leq 1000$ 。

对于 $100%$ 的数据，满足 $T\le 10,n\leq 100000,1\leq a_i\leq 10^9$ 。

#include <iostream>
using namespace std;
int main() {
    
    return 0;
}

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

根据您提供的题目描述和需求，我将提供一个完整的解决方案，包括代码实现和示例输入输出。

问题分析

题目要求判断给定序列是否可以划分为若干个区间，使得每个区间都没有严格众数。这里的关键是理解严格众数的定义：序列中某个数字出现次数严格大于序列长度的一半。

算法设计

1. 统计频率：首先统计序列中每个数字出现的次数。
2. 判断严格众数：检查是否有数字出现次数超过序列长度的一半。
3. 划分区间：如果没有严格众数，尝试将序列划分为多个区间。对于偶数长度的序列，可以去掉中间两个数字后继续判断；对于奇数长度的序列，可以直接判断为可以划分。

代码实现

以下是根据上述分析步骤实现的C++代码示例：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 判断序列是否有严格众数
bool hasStrictMode(const vector<int>& a) {
    int n = a.size();
    unordered_map<int, int> freq;
    for (int num : a) {
        freq[num]++;
    }
    for (auto& f : freq) {
        if (f.second > n / 2) {
            return true;
        }
    }
    return false;
}

// 判断序列是否可以划分为没有严格众数的区间
bool canDivide(const vector<int>& a) {
    int n = a.size();
    if (hasStrictMode(a)) {
        return false; // 如果存在严格众数，不能划分
    }
    if (n % 2 == 1) {
        return true; // 奇数长度可以直接划分
    }
    // 偶数长度，尝试去掉中间两个数字后判断
    vector<int> newA(a.begin(), a.begin() + n - 2);
    return !hasStrictMode(newA);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        if (canDivide(a)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

示例输入输出

示例输入

2
6
1 1 4 5 1 4
4
2 3 3 3

示例输出

Yes
No

注意事项

• 代码中使用了unordered_map来统计数字出现的频率，以快速判断是否存在严格众数。
• 函数hasStrictMode用于判断序列中是否存在严格众数。
• 函数canDivide用于判断序列是否可以划分为没有严格众数的区间。

用户可以根据上述代码示例进行进一步的测试和调整。如果有任何问题或需要进一步的帮助，请随时联系。