题解：P7633 [COCI 2010/2011 #5] BRODOVI

sandi_123 · 2026-06-11 09:36:29 · 题解

题解

:::warning[警告]{open} 这题不很水吗？多想一想再看题解吧！ :::

题目大意

有一些船只，从第一天开始每隔固定的时间就会来到港口。现在给出 n 个有船只来到的日子，求最少有多少只船。

思考过程

本题数据范围较小，可以使用贪心来完成。

这道题的核心是：每艘船从第 1 天开始，每隔固定的天数 d 访问一次。

所以，如果一个娱乐日是 a，那么它一定满足：

也就是说，a - 1 必须能被这艘船的周期 d 整除。

贪心策略

从小到大处理 b_i：

如果当前的 b_i 能被 已经选过的某个 d 整除，说明它已经被某艘船覆盖了。

否则，就必须新增一艘船，而这艘船的周期可以直接取 b_i 本身（因为 b_i 一定能整除自己）。

这样，我们每次只在新出现无法被覆盖的日子时才增加船只，保证了最少船只数量。

AC代码

#include<bits/stdc++.h>
using namespace std;

long long n,a[5010];
vector<long long> v;

int main()
{
    cin >> n;
    for (long long i = 1;i<=n;i++)
    {
        cin >> a[i];
        a[i]--; //全部减1，转化为周期问题
    }
    for (long long i = 2;i<=n;i++) //第一个是0，跳过
    {
        bool flag = 0;
        for (auto g:v)
            if(a[i]%g == 0) //能被已有周期整除，已被覆盖
            {
                flag = 1;
                break;
            }
        if(!flag) v.push_back(a[i]); //需要新船
    }
    cout << v.size(); //最少船只数
    return 0;
}