B4174 厂房 题解

· · 题解

B4174 厂房

思路分析

Ciallo～(∠・ω< )⌒★

这是一道很简单的贪心题，由于只需求分的最小组数，所以可以无脑分给左边，越长越好。
那么该如何判断当前的数能否分给左边呢？
在一个公差大于 1 等差数列中, 个个数之差的最小公倍数应大于 1 ，因此只需抓住这个点，并且额外注意每组中绝对不能出现相同数字。
具体细节代码解释。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, ans, a[N];
unordered_map <int, int> m; //使用 unordered_map 统计数字是否出现，比set更简单
void solve() {
    int gcd = 0, dif; //dif为两数差值
    m[a[1]] += 1;
    for(int i = 2; i <= n; i++) {
        dif = abs(a[i] - a[i-1]);
        if(m[a[i]] || __gcd(gcd, dif) <= 1) {
            ans ++, gcd = 0;
            m.clear(); //清空map
            m[a[i]] += 1; //一定要加，这是下一组的第一个数
        } else {
            gcd = __gcd(gcd, dif);
            m[a[i]] += 1;
        }
    }
    ans += 1; //最后一组无法在循环中被判断，因此补上一组
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    solve();
    cout << ans << '\n';
    return 0;
}