C++气球游戏：最小扎破数 - 算法题解

众所周知，ty奥信队的同学们早已回归校园，积极地备赛CSP - J/S，他们的暑假比别的同学少一大半，但是在每位同学身上都可以看到自信和快乐的光芒! 这是因为每天老师都会组织同学们进行体育锻炼，并且给同学们玩一些有趣的体育游戏，今天的游戏是这样的:

体育老师拿出n个气球从左到右排成一排，每个气球上面都会有一个数字编号ai。你可以选择扎破某一些气球，但是最多只能扎破n - 1个气球，至少要剩下一个气球留在场上

假设目前你已经扎破了一些气球，场上还剩下m个气球，那么胜利的规则是这m个气球中的每一个气球i(1 < i< m如果气球上的数字a;恰好等于i，那么你将赢得游戏的胜利!

由于你的体力有限，所以你需要找到最小的扎破气球的数目，使得你能获得游戏的胜利，并把这个最小的数目输出出来;而如果无论怎么扎破气球都没办法赢得胜利，那么输出-1.

输入格式

第一行输入一个整数n表示气球的数量

第二行输入n个整数a1 a2 ... an，表示第i个气球上写着的数字

输出格式

输出能赢得游戏胜利的，最小的扎破气球的个数。 如果不能赢得游戏，输出 -1.

C++内容：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
sort(nums.begin(), nums.end());

int result = -1;
for (int i = 0; i &lt; n; i++) {
    int count = 0;
    bool valid = true;
    for (int j = 0; j &lt; n; j++) {
        if (nums[j] &lt;= i) {
            count++;
        } else {
            valid = false;
            break;
        }
    }
    if (valid &amp;&amp; count == i) {
        result = i;
        break;
    }
}

cout &lt;&lt; result &lt;&lt; endl;

return 0;

}