Codeforces 1254B1 - Send Boxes to Alice (Easy Version)
阅读原文时间:2023年09月03日阅读:2

题意

有\(n(1\leq n\leq 10^5)\)个盒子,每个盒子有\(a_i(0\leq a_i \leq 1)\)个糖果,你每一次可以将第\(i\)个盒子里的糖果放到第\(i-1\)或\(i+1\)个盒子中(如果盒子存在)。最后要使每个盒子的糖果数量都整除\(k(k>1)\)(注意盒子可以为空),问最小操作数。

分析

\((1)\)因为糖果是类似于平铺的形式,堆叠时,我们可以发现所有存在糖果的盒子中数量均为\(k\)。若存在一个盒子中有\(2*k\)个糖果,在平铺到堆叠的过程中,将另外\(k\)个糖果分在更近的盒子能得到更小的答案。

\((2)\)设糖果总数为\(cnt\),所有存在糖果的盒子数量均为\(k\),我们又可以发现,最小的操作是将\(1\)~\(k\)、\(k+1\)~\(2k\)、……、\(i*k+1\)~\((i+1)*k\)放在一起,即将相邻的\(k\)个放在一堆。

\((3)\)对于某\(k\)个糖果,需要找到一个盒子,这个盒子到这\(k\)个糖果的距离最小(kNN算法)。我们将糖果看成数轴上的点,运用高一的绝对值知识(我忘了,我向高中数学老师谢罪)。

  • 若\(k\)为奇数,则将该盒子设置为最中间糖果所在的盒子
  • 若\(k\)为偶数,则将该盒子设置为最中间两个糖果中任意一个所在的盒子

即对于\(i*k+1\)~\((i+1)*k\)来说,第\(k-i/2\)个盒子,设其坐标为\(ave\)。

\((4)\)为降低时间复杂度,我们采取前缀的思想,\(sum[i]\)表示坐标\(i\)之前的糖果的坐标总和(没糖果的盒子不加),\(num[i]\)表示坐标\(i\)之前有多少糖果。

\((5)\)枚举可以被\(cnt\)整除的\(k\),模拟\((2)\)的过程,设\(first\)为第\(i*k+1\)个糖果的坐标,\(last\)为第\((i+1)*k\)个糖果的坐标,那么每个循环都得加上\((num[ave] - num[first - 1])*ave-(sum[ave] - sum[first - 1])+(sum[last] - sum[ave])-(num[last] - num[ave])*ave\),意思为\(ave\)之前的操作次数加上\(ave\)之后的操作次数,最后取最小值

\((6)\)记得开\(long\ long\),\(INF\)也记得开大一点。

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define LL long long
#define pii pair<int,int>
#define int ll
using namespace std;
const int maxn = (ll) 1e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f3f3f3f3f;
int a[maxn];
int cnt = 0;
int sum[maxn];
int num[maxn];

signed main() {
    start;
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        num[i] = num[i - 1] + x;//前缀数量
        if (x) {
            a[++cnt] = i;
            sum[i] = i;
        }
    }
    for (int i = 1; i <= n; ++i)//前缀坐标和
        sum[i] += sum[i - 1];
    int ans = inf;
    for (int i = 2; i <= cnt; ++i) {
        if (cnt % i == 0) {
            int tmp = 0;
            for (int k = i; k <= cnt; k += i) {//k为最后的糖果
                int first = a[k - i + 1];
                int last = a[k];
                int ave = a[k - i / 2];
                int num1 = num[ave] - num[first - 1];
                int num2 = num[last] - num[ave];
                int tot1 = sum[ave] - sum[first - 1];
                int tot2 = sum[last] - sum[ave];
                int t = num1 * ave - tot1 + tot2 - num2 * ave;
                tmp += t;
            }
            ans = min(ans, tmp);
        }
    }
    if (ans == inf)
        cout << -1;
    else
        cout << ans;
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章