设计一个c++程序,完成下列问题: 有一个由正整数组成的数组,可以移动数组中任意两个数的位置,当这两个数的差值小于等于1时可以消掉一个数。现输入一个整数t,代表有t组测试用例,测试用例包含两行,第一行为数组长度n,一第二行是n个数组元素。判断每个测试用例能否通过上述操作消到最后只剩一个数,可以输出“yes”,否则输出“no”
时间: 2024-03-22 15:41:58 浏览: 54
好的,根据你的要求,我为你设计了一个 C++ 程序,可以对多组测试用例进行判断,每组测试用例判断是否能通过上述操作消到最后只剩一个数。程序如下:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool canReduceToOne(int n, vector<int>& a) {
sort(a.begin(), a.end()); // 对数组进行排序
while (a.size() > 1) { // 只要数组长度大于1就一直执行下去
int i = 0;
while (i < a.size() - 1) {
if (a[i+1] - a[i] <= 1) { // 如果相邻两个数之差小于等于1,就消除它们
a.erase(a.begin() + i);
a.erase(a.begin() + i);
} else {
i++; // 否则继续寻找下一组相邻的数
}
}
if (a.size() == 0) return false; // 如果数组被消完了还没有剩下一个数,就返回 false
}
return true; // 如果最后只剩下一个数,就返回 true
}
int main() {
int t;
cout << "请输入测试用例数量:";
cin >> t;
for (int i = 1; i <= t; i++) {
int n;
cout << "请输入第 " << i << " 组测试用例的数组长度:";
cin >> n;
vector<int> a(n);
cout << "请输入第 " << i << " 组测试用例的数组元素:";
for (int j = 0; j < n; j++) {
cin >> a[j];
}
if (canReduceToOne(n, a)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
return 0;
}
```
这个程序使用了一个名为 `canReduceToOne` 的函数,该函数接受数组长度和数组本身作为参数,返回一个 bool 类型的值,表示该数组能否通过上述操作消到最后只剩一个数。程序首先会对数组进行排序,然后每次循环,都会寻找相邻两个数之差小于等于1的组合,并将它们消除。如果数组被消完了还没有剩下一个数,就返回 false。如果最后只剩下一个数,就返回 true。
在 `main` 函数中,程序会先要求输入测试用例数量,然后对每组测试用例进行输入,并调用 `canReduceToOne` 函数进行判断。如果返回值为 true,就输出 "yes",否则输出 "no"。
阅读全文