4322: 【基础】最大子集(1761)

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：2

题目描述

有 lns="http://www.w3.org/1998/Math/MathML">N 个互不相同的整数，另外给定一个正整数 lns="http://www.w3.org/1998/Math/MathML">T，定义两个整数 lns="http://www.w3.org/1998/Math/MathML">x,y（lns="http://www.w3.org/1998/Math/MathML">x≤y） 不冲突的条件为，lns="http://www.w3.org/1998/Math/MathML">y≠T×x。

请求出该集合的最大子集，要求子集中的元素互不冲突。

输入

第一行给定两个数 lns="http://www.w3.org/1998/Math/MathML">� 和 lns="http://www.w3.org/1998/Math/MathML">� （lns="http://www.w3.org/1998/Math/MathML">1≤�≤105, lns="http://www.w3.org/1998/Math/MathML">1≤�≤109）。

接下来一行包含 lns="http://www.w3.org/1998/Math/MathML">� 个不同正整数 lns="http://www.w3.org/1998/Math/MathML">��（ lns="http://www.w3.org/1998/Math/MathML">1≤��≤109）。

输出

输出最大互不冲突子集的数量。

样例输入 复制 

4 2
1 2 3 4

样例输出 复制 

3

提示

## 方法思路
1. **排序数组**：首先将数组排序，这样可以方便地处理元素之间的关系。
2. **贪心选择**：使用贪心算法，尽可能多地选择元素。对于每个元素，如果它不能被前面的元素通过T倍关系生成，就选择它。

3. **map记录**：使用map来记录已经被选择的元素，以便快速检查是否存在冲突。 

#include <bits/stdc++.h>
using namespace std;
using namespace std;
int main() {
    int N, T;
    cin >> N >> T;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    map<int, bool> selected;
    int count = 0;
    for (int num : a) {
        if (num % T != 0 || selected.find(num / T) == selected.end()) {
            selected[num] = true;
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

来源/分类

提交提交记录统计露一手!