环形 && 非环形 均分纸牌
非环形
解法实现 1 暴力枚举
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 110;
int a[N];
int main()
{
int n; cin >> n;
int aver = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
aver += a[i];
}
aver /= n;
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] - aver)
{
a[i + 1] += a[i] - aver;
ans++;
}
}
cout << ans << endl;
return 0;
}
解法实现 2 前缀和 + 贪心
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 10010;
int a[N];
int main()
{
int n; cin >> n;
int aver = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
aver += a[i];
}
aver /= n;
for (int i = 1; i <= n; i++)
{
a[i] -= aver;
}
int presum = 0, res = 0;
for (int i = 1; i <= n; i++)
{
presum += a[i];
if (presum)
{
res++;
}
}
cout << res << endl;
return 0;
}
解法实现3 前缀和
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 10010;
int a[N];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i - 1];
}
int ans = n;
int aver = a[n] / n;
for (int i = 1; i <= n; i++)
if (a[i] == aver * i)
ans--;
cout << ans << endl;
return 0;
}
环形
七夕祭前导题
基本公式推导解法
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll a[N], c[N];
int main()
{
int n; cin >> n;
ll tol = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
tol += a[i];
}
ll ave = tol / n;
for (int i = 2; i <= n; i++)
c[i] = c[i - 1] + a[i] - ave;
sort(c + 1, c + 1 + n);
ll mid = c[(n >> 1) + (n & 1)];
ll ans = 0;
for (int i = 1; i <= n; i++)
ans += abs(c[i] - mid);
cout << ans << endl;
return 0;
}
前缀和解法(最简便 )
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll a[N], s[N];
int main()
{
int n; cin >> n;
ll ave = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
ave += a[i];
}
ave /= n;
for (int i = 0; i < n; i++)
a[i] -= ave;
for (int i = 1; i < n; i++)
s[i] = a[i] + s[i - 1];
sort(s, s + n);
ll mid = s[n >> 1];
ll ans = 0;
for (int i = 0; i < n; i++)
ans += abs(s[i] - mid);
cout << ans << endl;
return 0;
}
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
int n, m, t;
ll row[N], col[N];
ll s[N];
int main()
{
cin >> n >> m >> t;
for (int i = 1; i <= t; i++)
{
int x, y;
cin >> x >> y;
row[x]++;
col[y]++;
} // 分列计算!
bool row_existed = false;
bool col_existed = false;
ll row_ans = 0, col_ans = 0;
if (!(t % n)) // row
{
row_existed = true;
memset(s, 0, sizeof s);
ll ave = t / n;
for (int i = 1; i <= n; i++)
row[i] -= ave;
for (int i = 1; i <= n; i++)
s[i] = row[i] + s[i - 1];
sort(s + 1, s + 1 + n);
ll mid = s[(n >> 1) + (n & 1)];
for (int i = 1; i <= n; i++)
row_ans += abs(s[i] - mid);
}
if (!(t % m)) // col
{
col_existed = true;
memset(s, 0, sizeof s);
ll ave = t / m;
for (int i = 1; i <= m; i++)
col[i] -= ave;
for (int i = 1; i <= m; i++)
s[i] = col[i] + s[i - 1];
sort(s + 1, s + 1 + m);
ll mid = s[(m >> 1) + (m & 1)];
for (int i = 1; i <= m; i++)
col_ans += abs(s[i] - mid);
}
if (col_existed && row_existed) cout << "both " << row_ans + col_ans << endl;
else if (col_existed) cout << "column " << col_ans << endl;
else if (row_existed) cout << "row " << row_ans << endl;
else puts("impossible");
return 0;
}