题意
有\(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算法)。我们将糖果看成数轴上的点,运用高一的绝对值知识(我忘了,我向高中数学老师谢罪)。
即对于\(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;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章