資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告