数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：检查能否通过选择盒子移除所有石头
假设我们有一个包含N个元素的数组A。考虑有N个盒子，它们呈圆形排列。第i个盒子包含A[i]块石头。我们必须检查是否可以通过重复执行以下操作来移除所有石头：选择一个盒子，例如第i个盒子。对于范围1到N中的每个j，从(i+j)个盒子中移除正好j块石头。(N+k)个盒子称为第k个盒子。如果一个盒子没有足够的石头，则无法执行此操作。
因此，如果输入类似于A = [4, 5, 1, 2, 3]，则输出为True，因为我们可以从第二个盒子开始移除所有石头。
为了解决这个问题，我们将遵循以下步骤：
n := size of A
Define an array a of size (n + 1)
Define an array b of size (n + 1)
sum := 0, p := n * (n + 1)
for initialize i := 1, when i <= n, update (increase i by 1), do:
a[i] := A[i - 1]
sum := sum + a[i]
if sum mod p is not equal to 0, then:
return false
k := sum / p
for initialize i := 1, when i <= n, update (increase i by 1), do:
b[i] := a[i] - a[(i mod n) + 1]
sum := 0
for initialize i := 1, when i <= n, update (increase i by 1), do:
a[i] := b[i]
sum := sum + a[i]
if sum is not equal to 0, then:
return false
for initialize i := 1, when i <= n, update (increase i by 1), do:
if (a[i] + k) mod n is not equal to 0 or a[i] + k < 0, then:
return false
return true示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A) {
int n = A.size();
vector<int> a(n + 1);
vector<int> b(n + 1);
int sum = 0, p = n * (n + 1) / 2;
for (int i = 1; i <= n; i++) {
a[i] = A[i - 1];
sum += a[i];
}
if (sum % p != 0) {
return false;
}
int k = sum / p;
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i % n + 1];
}
sum = 0;
for (int i = 1; i <= n; i++) {
a[i] = b[i];
sum += a[i];
}
if (sum != 0) {
return false;
}
for (int i = 1; i <= n; i++) {
if ((a[i] + k) % n != 0 || a[i] + k < 0) {
return false;
}
}
return true;
}
int main(){
vector<int> A = { 4, 5, 1, 2, 3 };
cout << solve(A) << endl;
}输入
{ 4, 5, 1, 2, 3 }
输出
1
更新于：2022年2月25日
124 次浏览
广告