3723. 最小公倍数

Deuchie

首先,在 WA 了一发后发现对 n = 1 的情况要特判一下输出1……

分析题意,可以得到性质1:

第一个天数和第二个天数之间的差,必然是一个最小间隔数(有一个小朋友)。

这是因为在第二个天数之前不存在其他的小朋友到达,所以这个间隔数必然是对的。把这个间隔数记录下来。

还有性质2:

后面的天数:

  • 如果能被已经记录的间隔数中的某一个整除,说明可能是之前的某个小朋友他又来了。
  • 如果不能被已经记录的间隔数整除,那么显然前面所有的记录天数没有用,而这一天和第一天的间隔数又是一个最小间隔数(类似性质1)。

根据这个性质写出代码:

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

int main() {
    int n;
    cin >> n;

    // Special Judge: n == 1, put 1.
    if (n == 1) {
        cout << "1\n";
        return EXIT_SUCCESS;
    }

    int dates[200000];
    vector<int> intervals;
    cin >> dates[0];    // first day is 1, not needed.
    for (int i = 1; i < n; ++i) {
        cin >> dates[i];
        --dates[i];     // -1 to show the interval.
        bool has_divisor = false;
        for (auto j : intervals)
            if (dates[i] % j == 0) {
                has_divisor = true;
                break;
            }
        if (has_divisor == false) {
            intervals.push_back(dates[i]);
        }
    }
    cout << intervals.size() << '\n';
}

复杂度是 $O(n^2)$,可以应对这题五次方的数据量。

Andrew-Malcom

include

using namespace std;
int main()
{
        int n;
        scanf("%d",&n);
        vector<int>num;
        vector<int>sd;
        for(int i=0;i<n;i++){
                int s;
                scanf("%d",&s);
                num.push_back(s);
        }
        int i,j,k=0,mass[n];
        for(i=1;i<num.size();i++){
                mass[k++]=num[i]-1;
        }
        sd.push_back(num[1]-num[0]);
        for(i=0;i<k;i++){
                for(j=0;j<sd.size();j++){
                        if(mass[i]%sd[j]==0){
                                break;
                        }
                }
                if(j>=sd.size()){
                        sd.push_back(mass[i]);
                }
        }
        printf("%d\n",sd.size());
}
ctttttry

下面是一个O(n)的C++实现,使用hash表空间换时间。

include

include

define maxn 200010

using namespace std;

int dates[maxn] = {0}; //所有记录日期
int hash_tag[maxn] = {0}; //hash_tag[i]标记第i天是否有人会来,初始化均为无人

int solve(int m)
{
int date, ans = 0, remains = m - 1; //remains记录剩下无人来的日期
for(int i = 1; i < m && remains > 0; i++)
{
date = dates[i];
if(hash_tag[date] == 0)//当这一天无人来时,需要安排一个人这天来
{
ans++;
while(date <= dates[m - 1] && remains > 0) //标记所有这个人会来的日期
{
if(hash_tag[date] == 0) //若无人来,则标记有,且剩余无人来的天数减少
{
hash_tag[date] = 1;
remains–;
}
date += (dates[i] - 1); //下次会来的日期
}
}
}
return ans;
}

int main(){
int n;
cin >> n;

for(int i = 0; i < n; i++)
    scanf("%d", &dates[i]);

if(n == 1)
    printf("1\n");
else
    printf("%d\n", solve(n));

}

你当前正在回复 博客/题目
存在问题!