题解：CF2227C Snowfall

· · 题解

CF 链接\ 洛谷题目

思路

简单分析后得到满足总乘积为 6 的倍数的两个条件：

  1. 区间内有 6 的倍数。
  2. 区间内有 2 的倍数和 3 的倍数。

所以考虑对数组 a 分成四类：

  1. 能被 6 整除的数。
  2. 能被 2 整除但不能被 3 整除的数。
  3. 能被 3 整数但不能被 2 整除的数。
  4. 既不能被 2 整除又不能被 3 整除的数。

要使 f(a) 最小，就要先放第一类或最后放第一类，且第二类和第三类间距离尽可能大。 \ 所以可按照第一类、第二类、第四类、第三类的顺序放置。

:::info[代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
void read(int &a);
void wr(int a) ;
void write(int a) ;
int t, n, temp;
signed main() {
    read(t);
    while (t--) {
        read(n);
        vector<int> a, b, c, d;//a为第一类，b为第二类，c为第三类，d为第四类。
        for (int i = 1; i <= n; i++) {
            read(temp);
            if (temp % 6 == 0) {
                a.push_back(temp);
            } else if (temp % 2 == 0) {
                b.push_back(temp);
            } else if (temp % 3 == 0) {
                c.push_back(temp);
            } else {
                d.push_back(temp);
            }
        }
        for (int i = 0; i < (int)a.size(); i++) {
            write(a[i]);
        }
        for (int i = 0; i < (int)b.size(); i++) {
            write(b[i]);
        }
        for (int i = 0; i < (int)d.size(); i++) {
            write(d[i]);
        }
        for (int i = 0; i < (int)c.size(); i++) {
            write(c[i]);
        }
        puts("");
    }
    return 0;
}

void read(int &a) {
    a = 0;
    int f = 1;
    char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c <= '9' && c >= '0') {
        a = (a << 3) + (a << 1) + c - 48;
        c = getchar();
    }
    a *= f;
}//快读
void wr(int a) {
    if (a <= 9) {
        putchar(a + 48);
        return ;
    } else {
        wr(a / 10);
    }
    putchar(a % 10 + 48);
}
void write(int a) {
    if (a < 0) {
        putchar('-');
        a = -a;
    }
    wr(a);
    putchar(' ');
}//快写

:::